Search

In this paper, we continue the study of a version of the paired-domination game recently introduced by the authors that embraces both the domination and the matching flavor of the game. The game is played on a graph G by two players, named Dominator and Staller. The players take turns choosing a pair of adjacent vertices of G such that neither vertex in the pair has yet been chosen and the vertices in the pair must dominate at least one vertex not dominated by the previously chosen vertices. This process eventually produces a paired-dominating set of vertices of G; that is, a dominating set in G that induces a subgraph that contains a perfect matching. The game paired-domination number γ gpr (G) of G is the number of vertices chosen when Dominator starts the game and both players play optimally, and the Staller-start game paired-domination number γ gpr ′ (G) of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper, we determine the game paired-domination numbers γ gpr (G) and γ gpr ′ (G) when the graph G is a path P n on n vertices. We show that γ gpr (P n) = 2 ⌈ n 3 ⌉ for all n ≥ 2 , unless n = 4 , in which case γ gpr (P n) = 2 , and we show that γ gpr ′ (P n) = 2 ⌈ n + 1 3 ⌉ for all n ≥ 2 , unless n ∈ { 3 , 9 } , in which case γ gpr ′ (P n) = 2 3 n . Moreover we describe optimal strategies for both Dominator and Staller for the paired-domination game played on a path. [ABSTRACT FROM AUTHOR]

Let G be a nontrivial connected graph with vertex set V (G) and the edge set E(G). A set S ⊆ V (G) is a geodetic hop dominating set of G if the following two conditions hold for each x ∈ V (G)\S: (1) x lies in some u-v geodesic in G with u, v ∈ S, and (2) x is of distance 2 from a vertex in S. The minimum cardinality γhg(G) of a geodetic hop dominating set of G is the geodetic hop domination number of G. A geodetic hop dominating set S is a minimal geodetic hop dominating set if S does not contain a proper subset that is itself a geodetic hop dominating set. The maximum cardinality of a minimal geodetic hop dominating set in G is the upper geodetic hop domination number of G, and is denoted by γ + hg(G). This paper initiates the study of the minimal geodetic hop dominating set and the corresponding upper geodetic hop domination number of nontrivial connected graphs. Interestingly, every pair of positive integers a and b with 2 ≤ a ≤ b is realizable as the geodetic domination number and the upper geodetic hop domination number, respectively, of some graph. Furthermore, this paper investigates the concept in the join, corona and lexicographic product of graphs. [ABSTRACT FROM AUTHOR]

The concept of vulnerability in a communication network plays an important role when there is a disruption in the network. There exist several graph parameters that measure the vulnerability of a communication network. Domination integrity is one of the vulnerability parameters that measure the performance of a communication network. In this paper, we introduce the concept of paired domination integrity of a graph as a new measure of graph vulnerability. Let G = (V,E) be a simple, connected graph. A set of vertices in a graph G, say S, is a paired dominating set if the following two conditions are satisfied: (i) every vertex of G has a neighbor in S and (ii) the subgraph induced by S contains a perfect matching. The paired domination integrity of G, denoted by PDI(G), is defined as PDI(G) = min{|S| + m(G − S) : S is a paired dominating set of G}, where m(G − S) is the order of the largest component in the induced subgraph of G − S. In this paper, we determine few bounds relating paired domination integrity with other graph parameters and the paired domination integrity of some classes of graphs. [ABSTRACT FROM AUTHOR]

This paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W [ 1 ] -hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parameterized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the Maximum Clique , Minimum Graph Coloring , (Total) Minimum Dominating Set , Minimum Vertex Cover and Maximum Independent Set problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above. [ABSTRACT FROM AUTHOR]

A total dominating set in a graph G $G$ is a set of vertices of G $G$ such that every vertex is adjacent to a vertex of the set. The total domination number γt(G) ${\gamma }_{t}(G)$ is the minimum cardinality of a total dominating set in G $G$. In this paper, we study the following open problem posed by Yeo. For each Δ≥3 ${\rm{\Delta }}\ge 3$, find the smallest value, rΔ ${r}_{{\rm{\Delta }}}$, such that every connected graph G $G$ of order at least 3, of order n $n$, size m $m$, total domination number γt ${\gamma }_{t}$, and bounded maximum degree Δ ${\rm{\Delta }}$, satisfies m≤12(Δ+rΔ)(n−γt) $m\le \frac{1}{2}({\rm{\Delta }}+{r}_{{\rm{\Delta }}})(n-{\gamma }_{t})$. Henning showed that rΔ≤Δ ${r}_{{\rm{\Delta }}}\le {\rm{\Delta }}$ for all Δ≥3 ${\rm{\Delta }}\ge 3$. Yeo significantly improved this result and showed that 0.1ln(Δ)

Let G be a finite simple graph. A set S ⊆ V (G) is a total hop dominating set of G if for every v ∈ V (G) , there exists u ∈ S such that d G (u , v) = 2. Any total hop dominating set of G of minimum cardinality is a γ th -set of G. A total hop dominating set S of G which intersects every γ th -set of G is a transversal total hop dominating set. The minimum cardinality γ ̂ th (G) of a transversal total hop dominating set in G is the transversal total hop domination number of G. In this paper, we initiate the study of transversal total hop domination in graphs. First, we characterize a graph G of order n for which γ ̂ th (G) is n or n − 1 , and also we determine the specific values of γ ̂ th (G) for some special graphs G. Next, we solve some realization problems involving γ ̂ th (G) with other parameters of G. Finally, we investigate the transversal total hop domination in the complementary prism, corona, and lexicographic product of graphs. [ABSTRACT FROM AUTHOR]

The strong nonsplit domsaturation number of a graph G , d s sns (G) is the least positive integer k such that every vertex of G lies in a strong nonsplit dominating set of cardinality k. In this paper, we obtain certain bounds for d s sns (G) and characterize the graphs which attain these bounds. [ABSTRACT FROM AUTHOR]

For a vertex v in a simple, finite and undirected graph G = (V (G) , E (G)) , the neighborhood N G (v) of v is the set consisting of all vertices of G which are adjacent to v. A perfect Italian dominating function on G is a function f : V (G) → { 0 , 1 , 2 } such that for each u ∈ V (G) with f (u) = 0 , ∑ x ∈ N G (u) f (x) = 2. The weight of a perfect Italian dominating function f is the value ω G (f) = ∑ v ∈ V (G) f (v). The perfect Italian domination number of G is the minimum weight of a perfect Italian dominating function on G. In this paper, we study the perfect Italian domination in graphs under some binary operations. [ABSTRACT FROM AUTHOR]

A set S ⊆ V of vertices in a graph G = (V , E) is called a dominating set if every vertex in V − S is adjacent to a vertex in S. Hamid defined a dominating set which intersects every maximum independent set in G to be an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by γ it (G). In this paper we prove that for trees T , γ it (T) is bounded above by ⌈ n 2 ⌉ and characterize the extremal trees. Further, we characterize the class of all trees whose independent transversal domination number does not alter owing to the deletion of an edge. [ABSTRACT FROM AUTHOR]

A Roman { 3 } -dominating function on a graph G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that for any vertex u ∈ V (G) , if f (u) = 0 , then ∑ v ∈ N G (u) f (v) ≥ 3 , and if f (u) = 1 , then ∑ v ∈ N G (u) f (v) ≥ 2. The weight of a Roman { 3 } -dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) and the minimum weight of a Roman { 3 } -dominating function on G is called the Roman { 3 } -domination number of G and is denoted by γ { R 3 } (G). Given a graph G , Roman { 3 } - domination asks to find the minimum weight of a Roman { 3 } -dominating function on G. In this paper, we study the algorithmic aspects of Roman { 3 } - domination on various graph classes. We show that the decision version of Roman { 3 } - domination remains NP -complete for chordal bipartite graphs, planar graphs, star-convex bipartite graphs, and chordal graphs. We show that Roman { 3 } - domination cannot be approximated within a ratio of (1 3 − ɛ) ln | V (G) | for any ɛ > 0 unless P = NP for bipartite graphs as well as chordal graphs, whereas Roman { 3 } - domination can be approximated within a factor of O (ln Δ) for graphs having maximum degree Δ. We also show that Roman { 3 } - domination is APX -complete for graphs with maximum degree 4. On the positive side, we show that Roman { 3 } - domination can be solved in linear time for chain graphs and cographs. [ABSTRACT FROM AUTHOR]

A set D ⊆ V of a graph G = (V , E) is called a connected power dominating set of G if G [ D ] , the subgraph induced by D , is connected and every vertex in the graph can be observed from D , following the two observation rules for power system monitoring: Rule 1 : if v ∈ D , then v can observe itself and all its neighbors, and Rule 2 : for an already observed vertex whose all neighbors except one are observed, then the only unobserved neighbor becomes observed as well. Given a graph G , Minimum Connected Power Domination is to find a connected power dominating set of minimum cardinality of G and Decide Connected Power Domination is the decision version of Minimum Connected Power Domination. Decide Connected Power Domination is known to be N P -complete for general graphs. In this paper, we prove that Decide Connected Power Domination remains N P -complete for star-convex bipartite graphs, perfect elimination bipartite graphs and split graphs. This answers some open problems posed in [B. Brimkov, D. Mikesell and L. Smith, Connected power domination in graphs, J. Comb. Optim. 38(1) (2019) 292–315]. On the positive side, we show that Minimum Connected Power Domination is polynomial-time solvable for chain graphs, a proper subclass of perfect elimination bipartite graph, and for threshold graphs, a proper subclass of split graphs. Further, we show that Minimum Connected Power Domination cannot be approximated within (1 −) ln | V | for any > 0 unless P = N P , for bipartite graphs as well as for chordal graphs. Finally, we show that Minimum Connected Power Domination is APX -hard for bounded degree graphs. [ABSTRACT FROM AUTHOR]

Harary and Wiener indices are distance-based topological index. In this paper, we study the relations of graph energy e(G) and its Harary index H(G) and Wiener index W(G). Moreover, for a given graph G we study the lower bound of H(G) e(G) and W(G) e(G) in terms of the number of vertices of G. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the unit-Jacobson graph, which is defined by the unit elements and the elements of the Jacobson radical of a commutative ring R with nonzero identity. We give relationships between this new graph concept and some special rings such as j-clean rings, UJ-rings, local rings, and cartesian rings. Moreover, we investigate the concepts of the dominating set, diameter, and girth on the unit-Jacobson graph. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple graph with no isolated vertices. A dominating set S of G is said to be a cosecure dominating set of G, if for every vertex v ∈ S there exists a vertex u ∈ V ∖S such that uv ∈ E and (S∖{v}) ∪{u} is a dominating set of G. The Minimum Cosecure Domination problem is to find a minimum cardinality cosecure dominating set of G. In this paper, we show that the decision version of the problem is NP-complete for split graphs, undirected path graphs (subclasses of chordal graphs), and circle graphs. We also present a linear-time algorithm to compute the cosecure domination number of cographs (subclass of circle graphs). In addition, we present a few results on the approximation aspects of the problem. [ABSTRACT FROM AUTHOR]

A vertex subset D of a graph G = (V, E) is said to be a dominating set if every vertex in G is either in D or adjacent to some vertex in D. The minimum cardinality of such a set is the domination number, which is denoted as γ(G). In this paper, we define a sequence associated with the domination concept in graphs and study the basic properties of the sequence in terms of various parameters of graphs. Using this sequence we order the vertices of a dominating set according to its significance and propose Equally Significant Dominating (ESD) graphs. We also introduced domination-related topological indices and computed their lower bounds for trees, unicyclic graphs and bicyclic graphs. All the graphs attaining the bounds are characterized. [ABSTRACT FROM AUTHOR]

A majority double Roman dominating function (MDRDF) on a graph G = (V , E) is a function f : V → { − 1 , + 1 , 2 , 3 } such that (i) every vertex v with f (v) = − 1 is adjacent to at least two vertices assigned with 2 or to at least one vertex w with f (w) = 3 , (ii) every vertex v with f (v) = 1 is adjacent to at least one vertex w with f (w) ≥ 2 and (iii) ∑ u ∈ N [ v ] f (u) ≥ 1 , for at least half of the vertices in G. The weight of an MDRDF is the sum of its function values over all vertices. The majority double Roman domination number of a graph G , denoted by γ MDR (G) , is defined as γ MDR (G) = min { w (f)   |   f   is an  MDRDF  of   G }. In this paper, we introduce and study the majority double Roman domination number on some classes of graphs. [ABSTRACT FROM AUTHOR]

Given a graph G with no isolated vertices, let γ e v (G) , i e v (G) , β e v (G) , γ (G) , γ pr (G) and Γ pr (G) denote the ev-domination number, the independent ev-domination number, the upper independent ev-domination number, the domination number, the paired-domination number and the upper paired-domination number, respectively. It is known that γ e v (G) = i e v (G) = 1 2 γ pr (G) ≤ β e v (G). In this paper, we extend this inequality chain to involve the upper paired-domination number for arbitrary graphs G with no isolated vertices as well as the domination number for trees. Moreover, we show that recognizing well ev-covered graphs (i.e., graphs G with i e v (G) = β e v (G)) is co-NP-complete, solving an open problem posed by Boutrig and Chellali. [ABSTRACT FROM AUTHOR]

A dominating set D of a graph G = (V , E) is said to be certified, if every vertex v ∈ D has either 0 neighbors or at least two neighbors in V\D. The cardinality of a minimum certified dominating set of G is called the certified domination number of G and is denoted by γ cer (G). A graph G is said to be γ cer - E A stable if for any two vertices u , v ∈ V (G) such that u v ∉ E (G) , we have γ cer (G + u v) = γ cer (G). In this paper, we provide upper bounds for the γ cer -value of γ cer - E A stable graph. We also characterize the trees and unicyclic graphs that are γ cer - E A stable. [ABSTRACT FROM AUTHOR]

Graphs considered here are simple, finite and undirected. A graph is denoted by G and its vertex set by V (G) and edge set by E (G). Many researchers were attracted by two concepts introduced in [P. J. Slater, Domination and location in acyclic graphs, Networks17 (1987) 55–64; P. J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988) 445–455; Y. Caro, A. Hansberg and M. Henning, Fair domination in graphs, Discrete Math. 312 (2012) 2905–2914]. One is locating domination and the other is fair domination. A subset D of V (G) is called a locating dominating set of G if for any u , v ∈ V − D , N (u) ∩ D ≠ N (v) ∩ D and both sets are non-empty. D is called a fair dominating set of G for any u , v ∈ D , | N (u) ∩ D | = | N (v) ∩ D | > 0. In this paper, both properties are combined and locating fair domination is studied. [ABSTRACT FROM AUTHOR]

The aim of this paper is to propose an Eulerian type of numerical finite difference approximation on structured grids for an advection dominated level set equation enhanced with a small curvature term. The proposed numerical scheme is based on upwind discretization in both the advection and the curvature term. This class of approximations is used in algebraic solvers, such as fast sweeping or fast marching methods, which respect the causality of solutions for which any information is propagating along characteristics, in order to solve the algebraic system in a finite number of computationally simple iterations or updates. An implicit numerical scheme for a time relaxed level set equation with non-zero right-hand side is used in this paper and solved by a nonlinear fast sweeping method. The results of the von Neumann stability analysis of the proposed scheme are presented, and numerical examples are used to verify the analysis. [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, S is an independent set, then S is an independent dominating set, while if every vertex of the dominating set S is adjacent to a vertex in S , then S is a total dominating set of G. A fundamental problem in domination theory in graphs is to determine which graphs have the property that their vertex set can be partitioned into two types of dominating sets. In particular, we are interested in graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set. In this paper, we solve this problem by providing a constructive characterization of such graphs. We show that all such graphs can be constructed starting from two base graphs and applying a sequence of eleven operations. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A set S ⊆ V is a total restrained dominating set if every vertex is adjacent to a vertex in S , and every vertex in V − S is adjacent to a vertex in V − S. The total restrained domination number of G , denoted γ t r (G) , is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K 1 , ℓ -free graph with δ ≥ ℓ ≥ 3 and δ ≥ 5 , then γ t r (G) ≤ n 1 − (2 δ − 3) (2 δ) δ δ − 1 + o δ (1) . [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V and edge set E , a vertex set D is a dominating set (DS) of G , if every vertex v ∈ V is either in D or adjacent to a vertex in D. If D is a DS of G and for every vertex v ∈ V ∖ D there exists a vertex u ∈ D adjacent to v such that (D ∖ { u }) ∪ { v } is also a DS of G , then D is a secure dominating set (SDS). The minimum secure dominating set problem (MinSDS) is to find an SDS of G with the minimum cardinality. In this paper, we design PTASs for MinSDS on planar graphs and growth-bounded graphs, that is, the computed solutions approximate the optimal value within factor (1 + ɛ) for any constant ɛ ∈ (0 , 1). [ABSTRACT FROM AUTHOR]

For a digraph Γ , a subset C of V (Γ) is a perfect code if C is a dominating set such that every vertex of Γ is dominated by exactly one vertex in C. In this paper, we classify strongly connected 2-valent Cayley digraphs on abelian groups admitting a perfect code, and determine completely all perfect codes of such digraphs. [ABSTRACT FROM AUTHOR]

A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex u ⁄ ∈ S , there is a vertex v ∈ S such that u v is an edge and (S ∖ { v }) ∪ { u } is also a dominating set of G. The secure domination number of G , denoted by γ s (G) , is the cardinality of a smallest secure dominating sets of G. In this paper, we prove that, for any outerplanar graph with n ≥ 4 vertices, γ s (G) ≥ (n + 4) / 5 and the bound is tight. [ABSTRACT FROM AUTHOR]

The domination game is played on a graph G by two players, Dominator and Staller, who alternate in selecting vertices until each vertex in the graph G is contained in the closed neighbourhood of the set of selected vertices. Dominator's aim is to reach this state in as few moves as possible, whereas Staller wants the game to last as long as possible. In this paper, we prove that if G has n vertices and minimum degree at least 2, then Dominator has a strategy to finish the domination game on G within 10 n / 17 + 1 / 17 moves, thus making progress towards a conjecture by Bujtás, Iršič and Klavžar. [ABSTRACT FROM AUTHOR]

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex in S. Recently, the following question was proposed: "Is it true that every connected cubic graph containing a 3-cycle has two vertex disjoint total dominating sets?" In this paper, we give a negative answer to this question. Moreover, we prove that if we replace 3-cycle with 4-cycle the answer is affirmative. This implies every connected cubic graph containing a diamond (the complete graph of order 4 minus one edge) as a subgraph can be partitioned into two total dominating sets, a result that was proved in 2017. [ABSTRACT FROM AUTHOR]

The notion of the metric dimension of a graph is well-known and its study is well entrenched in the literature. In this paper, we introduce new classes of graphs that exhibit remarkable characteristic: the metric dimension and the diameter of the unit graph are equal. Additionally, we provide a characterization of finite commutative rings R, wherein the metric dimension assumes a value k, where 1 ≤ k ≤ 3. Further, we also demonstrate an exhaustive examination that ascertains the precise finite commutative rings R, in which domination number is equal to metric dimension of unit graph. [ABSTRACT FROM AUTHOR]

AbstractWe define a total coalition in a graph G as a pair of disjoint subsets A1,A2 ⊆ A that satisfy the following conditions: (a) neither A1 nor A2 constitutes a total dominating set of G, and (b) A1 ∪ A2 constitutes a total dominating set of G. A total coalition partition of a graph G is a partition ϒ = {A1,A2, . . . ,Ak} of its vertex set such that no subset of ϒ acts as a total dominating set of G, but for every set Ai ∈ ϒ, there exists a set Aj ∈ ϒ such that Ai and Aj combine to form a total coalition. We define the total coalition number of G as the maximum cardinality of a total coalition partition of G, and we denote it by Ct(G). The purpose of this paper is to begin an investigation into the characteristics of total coalition in graphs. [ABSTRACT FROM AUTHOR]

Let G be a connected graph and uv ∈ E(G). We say, the vertex v even sum dominates u (u even sum dominates v) if deg(v)+deg(u) is an even number. A set S is an even sum dominating set (ESDS) if every vertex v ∈ V is either in S or even sum dominated by a vertex in S. An even sum dominating set S is a mimimal even sum dominating set if no proper subset S'⊂ S is an even sum dominating set. The even sum domination number γes(G) of a graph G is the minimum cardinality of an even sum dominating set of G. In this paper, we discuss some properties and bounds for this concept. We also derive even sum domination number for some standard graphs. [ABSTRACT FROM AUTHOR]

Let G = (V (G), E(G)) be a simple and undirected graph. A dominating set S ⊆ V (G) is called a differentiating odd dominating set if for every vertex v ∈ V (G), |N[v] ∩ S| ≡ 1(mod 2) and NG[u] ∩ S≠ NG[v] ∩ S for every two distinct vertices u and v in V (G). The minimum cardinality of a differentiating odd dominating set of G, denoted by γo D(G), is called the differentiating odd domination number. In this paper, we discuss differentiating odd dominating sets and give bounds or exact values of the differentiating odd domination numbers of some graphs. We give necessary and sufficient conditions for some graphs to admit a differentiating odd dominating set. Moreover, we characterize the differentiating odd dominating sets in graphs resulting from join, corona, and lexicographic product of some graphs and determine the differentiating odd domination numbers of these graphs. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. A set S ⊆ V (G) is convex 2-dominating if S is both convex and 2-dominating. The minimum cardinality among all convex 2-dominating sets in G, denoted by γ2con(G), is called the convex 2-domination number of G. In this paper, we initiate the study of convex 2- domination in graphs. We show that any two positive integers a and b with 6 ≤ a ≤ b are, respectively, realizable as the convex domination number and convex 2-domination number of some connected graph. Furthermore, we characterize the convex 2-dominating sets in the join, corona, lexicographic product, and Cartesian product of two graphs and determine the corresponding convex 2-domination number of each of these graphs. [ABSTRACT FROM AUTHOR]

For k ≥ 1, in a graph G = (V, E), a set of vertices D is a distance kdominating set of G, if any vertex in V \ D is at distance at most k from some vertex in D. The minimum cardinality of a distance k-dominating set of G is the distance k-domination number, denoted by γk(G). An ordered set of vertices W = {w1, w2, . . ., wr} is a resolving set of G, if for any two distinct vertices x and y in V \ W, there exists 1 ≤ i ≤ r such that dG(x, wi) 6= dG(y, wi). The minimum cardinality of a resolving set of G is the metric dimension of the graph G, denoted by dim(G). In this paper, we introduce the distance k-resolving dominating set which is a subset of V that is both a distance k-dominating set and a resolving set of G. The minimum cardinality of a distance k-resolving dominating set of G is called the distance k-resolving domination number and is denoted by γkr(G). We give several bounds for γkr(G), some in terms of the metric dimension dim(G) and the distance k-domination number γk(G). We determine γkr(G) when G is a path or a cycle. Afterwards, we characterize the connected graphs of order n having γkr(G) equal to 1, n - 2, and n - 1, for k ≥ 2. Then, we construct graphs realizing all the possible triples (dim(G), γk(G), γkr(G)), for all k ≥ 2. Later, we determine the maximum order of a graph G having distance k-resolving domination number γkr(G) = γr k ≥ 1, we provide graphs achieving this maximum order for any positive integers k and γkr. Then, we establish Nordhaus-Gaddum bounds for γkr(G), for k ≥ 2. Finally, we give relations between γkr(G) and the k-truncated metric dimension of graphs and give some directions for future work. [ABSTRACT FROM AUTHOR]

Let G be a graph with no isolated vertex. A set D ⊆ V (G) is a total dominating set of G if every vertex of G is adjacent to at least one vertex in D. The total domination number of G, denoted by γt(G), is the minimum cardinality among all total dominating sets of G. In this paper we study the total domination number of total graphs T(G) of simple graphs G. In particular, we give some relationships that exist between γt(T(G)) and other domination parameters of G and of some well-known graph operators on G. Finally, we provide closed formulas on γt(T(G)) for some well-known families of graphs G. [ABSTRACT FROM AUTHOR]

Let G = G(V,E) be a graph. A set S U V is a power dominating set of G if S observes all the vertices in V, following two rules: domination and propagation. The cardinality of a minimum power dominating set is called the power domination number. In this paper, we compute the power domination number of generalized m-Mycielskian of a cycle, Cn. We found that it depends on the numbers n and m. [ABSTRACT FROM AUTHOR]

A coloring C = (V1,...,Vk) of G partitions the vertex set V (G) into independent sets Vi which are said to be color classes with respect to the coloring C. A vertex v is said to have a dominator (dom) color class in C if there is color class Vi such that v is adjacent to all the vertices of Vi and v is said to have an anti-dominator (anti-dom) color class in C if there is color class Vj such that v is not adjacent to any vertex of Vj. Dominator coloring of G is a coloring C of G such that every vertex has a dom color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G, denoted by χd(G). Global Dominator coloring of G is a coloring C of G such that every vertex has a dom color class and an anti-dom color class. The minimum number of colors required for a global dominator coloring of G is called the global dominator chromatic number of G, denoted by χgd(G). In this paper, we give a counterexample for the conjecture posed in [I. Sahul Hamid, M.Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39 (2019), 325-339] that for a graph G, if Xgd(G) = 2χd(G), then G is a complete multipartite graph. We deduce upper and lower bound for the global dominator chromatic number of Mycielskian of the graph G in terms of dominator chromatic number of G. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E), a function f: V → {0, 1, 2, 3, 4} is a triple Roman dominating function (TRDF) of G, for each vertex v ∈ V, (i) if f (v) = 0, then v must have either one neighbour in V4, or either two neighbours in V2 ∪ V3 (one neighbour in V3) or either three neighbours in V2, (ii) if f (v) = 1, then v must have either one neighbour in V3 ∪ V4 or either two neighbours in V2, and if f (v) = 2, then v must have one neighbour in V2 ∪ V3 ∪ V4. The triple Roman domination number of G is the minimum weight of an TRDF f of G, where the weight of f is v V f (v). The triple Roman domination problem is to compute the triple Roman domination number of a given graph. In this paper, we study the triple Roman domination problem. We show that the problem is NP-complete for the star convex bipartite and the comb convex bipartite graphs and is APX-complete for graphs of degree at most 4. We propose a linear-time algorithm for computing the triple Roman domination number of proper interval graphs. We also give an (2H (Δ(G) + 1) - 1)-approximation algorithm for solving the problem for any graph G, where Δ(G) is the maximum degree of G and H (d) denotes the first d terms of the harmonic series. In addition, we prove that for any ε > 0 there is no (1/4 - ε) ln |V |-approximation polynomial-time algorithm for solving the problem on bipartite and split graphs, unless NP ⊆ DTIME (|V |O(log log |V |)). [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph. A dominating set S ⊆ V (G) of G is a restrained dominating set in G if for every v ∈ V (G)S there exists u ∈ V (G)S such that uv ∈ E(G). A restrained dominating set S of G is a 1-movable restrained-dominating set of G if for every v ∈ S either S {v} is a restrained dominating set of G or there exists u ∈ (V(G)S) ∩ N(v) such that (S{v}) ∪ {u} is a restrained dominating set of G. The minimum cardinality of a 1-movable restrained-dominating set in G, denoted by γ¹mr(G), is the 1-movable restrained-domination number of G. In this paper, the 1-movable restrained-dominating sets in the corona of graphs are characterized. Also, the 1-movable restrained-dominationnumbers of these graphs are determined. [ABSTRACT FROM AUTHOR]

The middle graph M (G) of a graph G is the graph obtained by subdividing each edge of G exactly once and joining all these newly introduced vertices of adjacent edges of G. It is known that the decision problems for Italian domination number γ I (G) , 2 -rainbow domination number γ r 2 (G) and Roman domination number γ R (G) are NP-complete. Recently, it was proved that γ I (M (G)) = γ r 2 (M (G)) = γ R (M (G)) = n for a graph G of order n. In this paper, we continue to study several domination and domatic numbers in middle graphs. We also obtain closed formulas for domination, secure domination and total domination numbers in middle graphs of rooted product graphs. [ABSTRACT FROM AUTHOR]

Consider a graph G with vertex set V(G) and edge set E(G). A subset D of V(G) is said to be a dominating set of G if every vertex not in D is adjacent to at least one vertex in D. If, in addition, every vertex not in a dominating set R of G is adjacent to at least one vertex in V (G) - R , then R is called a restrained dominating set of G. A paired restraint dominating set S of a graph G is a restrained dominating set of G satisfying that the induced subgraph by S contains a perfect matching. The problems of computing the dominating set, restrained dominating set, and paired restraint dominating set with minimum cardinality are referred to as the domination, restrained domination, and paired restraint domination problems, respectively. The paired restraint domination problem and its applications are first proposed here. Our focus is on examining the complexity of the proposed problem on extended supergrid graphs and their subclasses, which include grid, diagonal supergrid, and (original) supergrid graphs. The domination problem is known to be NP-complete on grid graphs and, therefore, also on extended supergrid graphs. Our previous research demonstrated that the domination and restrained domination problems on diagonal and original supergrid graphs are NP-complete. However, the complexity of the paired restraint domination problem on grid, diagonal supergrid, and original supergrid graphs remains unknown. The NP-completeness of the paired restraint domination problem on diagonal supergrid graphs is demonstrated in this paper, and this finding is also applicable to the original supergrid graphs and planar graphs with maximum degree 4. We then examine a subclass of diagonal and original supergrid graphs known as rectangular supergrid graphs. These graphs are distinguished by a rectangular shape consisting of m rows and n columns of vertices. Specifically, we address the paired restraint domination problem on R m × n and develop a linear time algorithm for 3 ⩾ m ⩾ 1 and n ⩾ m . Then, when n ⩾ m ⩾ 4 , we obtain a tight upper bound on the minimum size of the paired restraint dominating set of R m × n and then use this upper bound to establish one lower bound. [ABSTRACT FROM AUTHOR]

A proper vertex coloring of G is a dominated coloring if each color class is dominated by at least one vertex of G, that is, for each color class there exists a vertex that is adjacent to all the vertices of the class. The dominated chromatic number χ dom (G) is the minimum number of colors needed for a dominated coloring of G. In this paper, we obtain the dominated chromatic number for circulant network, Sierpiński network, chain silicate network, and cyclic silicate network. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple graph and f: V → {0, 1, 2, 3} be a function. A vertex u with f (u) = 0 is called an undefended vertex with respect to f if it is not adjacent to a vertex v with f(v) ≥ 2. We call the function f a generous Roman dominating function (GRDF) if for every vertex with f (u) = 0 there exists at least a vertex v with f(v) ≥ 2 adjacent to u such that the function f′: V → {0, 1, 2, 3}, defined by f′(u) = α, f′(v) = f(v) - α where α = 1 or 2, and f′(w) = f(w) if w ∈ V - {u, v} has no undefended vertex. The weight of a generous Roman dominating function f is the value f(V) = P u∈V f(u). The minimum weight of a generous Roman dominating function on a graph G is called the generous Roman domination number of G, denoted by γgR (G). In this paper, we initiate the study of generous Roman domination and show its relationships. Also, we give the exact values for paths and cycles. Moreover, we present an upper bound on the generous Roman domination number, and we characterize cubic graphs G of order n with γgR (G) = n-1, and a Nordhaus-Gaddum type inequality for the parameter is also given. Finally, we study the complexity of this parameter. [ABSTRACT FROM AUTHOR]

Let be a graph of order . For , the set is defined as the external neighborhood of such that all vertices in have at least one neighbor in . The differential of is defined to be , and the 2-packing differential of a graph is defined as A function with the sets , where is a unique response Roman dominating function if implies that and implies that . The unique response Roman domination number of , denoted by , is the minimum weight among all unique response Roman dominating functions on . Let be the complement of a graph . The complementary prism of is the graph formed from the disjoint union of and by adding the edges of a perfect matching between the respective vertices of and . The present paper deals with the computation of the 2-packing differential and the unique response Roman domination of the complementary prisms by the use of a proven Gallai-type theorem. Particular attention is given to the complementary prims of special types of graphs. Furthermore, the graphs such that and are small are characterized. [ABSTRACT FROM AUTHOR]

Claude Berge (1987) introduced the concept of k-extendable graphs, wherein any independent set of size k is inherently a constituent of a maximum independent set within a graph H = (V , E) . Graphs possessing the property of being 1-extendable are termedas Berge graphs. This introduction gave rise to the notion of well-covered graphs and well-dominated graphs. A graph is categorized as well-covered if each of its maximal independent sets is, in fact, a maximum independent set. Similarly, a graph attains the classification of well-dominated if every minimal dominating set (DS) within it is a minimum dominating set. In alignment with the concept of k-extendable graphs, the framework of (k , γ) -endowed graphs and symmetric (k , γ) -endowed graphs are established. In these graphs, each DS of size k encompasses a minimum DS of the graph. In this article, a study of γ -endowed dominating sets is initiated. Various results providing a deep insight into γ -endowed dominating sets in graphs such as those characterizing the ones possessing a unique minimum DS are proven. We also introduce and study the symmetric γ -endowed graphs and minimality of dominating sets in them. In addition, we give a solution to an open problem in the literature. which seeks to find a domination-based parameter that has a correlation coefficient of ρ > 0.9967 with the total π -electronic energy of lower benzenoid hydrocarbons. We show that the upper dominating number Γ (H) studied in this paper delivers a strong prediction potential. [ABSTRACT FROM AUTHOR]

In this paper, we characterize trees with a strong secure domination number less than or equal to 4 and compute this parameter for certain classes of graphs. Also, we investigate bounds for the strong secure domination number of vertex gluing of two graphs. [ABSTRACT FROM AUTHOR]