Search

Abstract Let G = (V , E) be a graph and t , r be positive integers. The reception strength (or signal) that a vertex v receives from a tower of signal strength t located at vertex T is defined as s i g (v , T) = m a x (t − d i s t (v , T) , 0) , where d i s t (v , T) denotes the distance between the vertices v and T. In 2015 Blessing, Insko, Johnson, and Mauretour defined a (t , r) broadcast dominating set , or simply a (t , r) broadcast , on G as a set T ⊆ V such that the sum of all signals received at each vertex v ∈ V is at least r. We say that T is optimal if | T | is minimal among all such sets T. The cardinality of an optimal (t , r) broadcast on a finite graph G is called the (t , r) broadcast domination number of G. The concept of (t , r) broadcast domination generalizes the classical problem of domination on graphs. In fact, the (2 , 1) broadcasts on a graph G are exactly the dominating sets of G. In their paper, Blessing et al. considered (t , r) ∈ { (2 , 2) , (3 , 1) , (3 , 2) , (3 , 3) } and gave optimal (t , r) broadcasts on G m , n , the grid graph of dimension m × n , for small values of m and n. They also provided upper bounds on the optimal (t , r) broadcast numbers for grid graphs of arbitrary dimensions. In this paper, we define the density of a (t , r) broadcast, which allows us to provide optimal (t , r) broadcasts on the infinite grid graph for all t ≥ 2 and r = 1 , 2 , and bound the density of the optimal (t , 3) broadcast for all t ≥ 2. In addition, we present a Python program to compute upper bounds on the density of a minimal (t , r) broadcast on the infinite grid, and compute these bounds for all 1 ≤ t ≤ 15 and 1 ≤ r ≤ 40. Lastly, we construct a family of counterexamples to the conjecture of Blessing et al. that the optimal (t , r) and (t + 1 , r + 2) broadcasts are identical for all t ≥ 1 and r ≥ 1 on the infinite grid. [ABSTRACT FROM AUTHOR]

In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G , we define for every subset X of S the predicate S E C ( X ) = t r u e if and only if | N [ X ] ∩ S | ≥ | N [ X ] ∖ S | holds, where N [ X ] is a closed neighbourhood of X in graph G . A set S is a defensive alliance if and only if for each vertex v ∈ S we have S E C ( { v } ) = t r u e . If S is also a dominating set of G (i.e., N [ S ] = V ( G ) ), we say that S is a global defensive alliance . We introduce the concept of defensive sets in graph G as follows: set S is a defensive set in G if and only if for each vertex v ∈ S we have S E C ( { v } ) = t r u e or there exists a neighbour u of v such that u ∈ S and S E C ( { v , u } ) = t r u e . Similarly, if S is also a dominating set of G , we say that S is a global defensive set . We also study the problems of total dominating alliances ( total alliances ) and total dominating defensive sets ( total defensive sets ), i.e., S is a dominating set and the induced graph G [ S ] has no isolated vertices. In the paper we proved the NP -completeness for planar bipartite subcubic graphs of the decision versions of the following minimalization problems: a global and total alliance, a global and total defensive set. We proposed polynomial time algorithms solving in trees the problem of finding the minimum total and global defensive set and the total alliance. We obtained the lower bound on the minimum size of a global defensive set in arbitrary graphs and trees. [ABSTRACT FROM AUTHOR]

• Ecosystem services governance is shaped by power asymmetries. • There is a need for novel approaches that unravel the nature and intensity of power asymmetries. • Social network analysis can be used to investigate the different forms of power handled by actors. • Some forms of power, such as domination, strongly increase conflict probability. Power asymmetries affect the governance of natural resources but are rarely considered explicitly in ecosystem services research, which often overlooks the diversity of actors and their interactions. In this paper, we propose an innovative and easily replicable method to analyze two types of power asymmetries, using social network analysis and a power typology which distinguishes between influence and domination. We apply this method to a network of actors involved in the governance of eight ecosystem services in the Peruvian Andes. The results reveal substantial power asymmetries, of different types. Indirect managers of ecosystem services had higher influence and domination than the direct managers and beneficiaries. Businesses showed significantly lower influence than members of civil society, non-governmental organizations, and the public sector (state or decentralized organizations, public enterprises). Compared to other actors, members of the public sector had significantly higher domination, especially national actors. Domination and influence relationships strongly increased conflict probability, along with difference of domination score between two actors. A better interdisciplinary understanding of the determinants of power asymmetries can make the governance of socio-ecological systems more sustainable. [ABSTRACT FROM AUTHOR]

In this paper, we continue the study of neighborhood total domination in graphs first studied by Arumugam and Sivagnanam (2011). A neighborhood total dominating set, abbreviated NTD-set, in a graph G is a dominating set S in G with the property that the subgraph induced by the open neighborhood of the set S has no isolated vertex. The neighborhood total domination number, denoted by γ nt ( G ) , is the minimum cardinality of a NTD-set of G . Every total dominating set is a NTD-set, implying that γ ( G ) ≤ γ nt ( G ) ≤ γ t ( G ) , where γ ( G ) and γ t ( G ) denote the domination and total domination numbers of G , respectively. Arumugam and Sivagnanam posed the problem of characterizing the connected graphs G of order n ≥ 3 achieving the largest possible neighborhood total domination number, namely γ nt ( G ) = ⌈ n / 2 ⌉ . A partial solution to this problem was presented by Henning and Rad (2013) who showed that 5-cycles and subdivided stars are the only such graphs achieving equality in the bound when n is odd. In this paper, we characterize the extremal trees achieving equality in the bound when n is even. As a consequence of this tree characterization, a characterization of the connected graphs achieving equality in the bound when n is even can be obtained noting that every spanning tree of such a graph belongs to our family of extremal trees. [ABSTRACT FROM AUTHOR]

A twin dominating set in a digraph D = ( V , A ) is a set S ⊆ V such that, for every w ∈ V ∖ S , there exist arcs ( u , w ) , ( w , v ) ∈ A with u , v ∈ S . A twin dominating set S is efficient if there is no arc in the subdigraph induced by S and, for every w ∈ V ∖ S , there exist exactly one vertex u ∈ S and exactly one vertex v ∈ S such that arcs ( u , w ) , ( w , v ) ∈ A . This paper resolves a conjecture regarding an efficient twin domination set in generalized De Bruijn digraphs. The conjecture says that the generalized De Bruijn digraphs G B ( n , d ) with n a multiple of d + 1 have an efficient twin dominating set if and only if d is even and relatively prime to n . This paper affirms this conjecture. [ABSTRACT FROM AUTHOR]

Let G be a graph and γ (G) denote the domination number of G , i.e. the cardinality of a smallest set of vertices S such that every vertex of G is either in S or adjacent to a vertex in S. Matheson and Tarjan conjectured that a plane triangulation with a sufficiently large number n of vertices has γ (G) ≤ n ∕ 4. Their conjecture remains unsettled. In the present paper, we show that: (1) a maximal outerplane graph with n vertices has γ (G) ≤ ⌈ n + k 4 ⌉ where k is the number of pairs of consecutive degree 2 vertices separated by distance at least 3 on the boundary of G ; and (2) a Hamiltonian plane triangulation G with n ≥ 23 vertices has γ (G) ≤ 5 n ∕ 16. We also point out and provide counterexamples for several recent published results of Li et al. (2016) on this topic which are incorrect. [ABSTRACT FROM AUTHOR]

A set D of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to a vertex in D and the subgraph induced by D contains a perfect matching (not necessarily as an induced subgraph). A paired-dominating set of G is minimal if no proper subset of it is a paired-dominating set of G. The upper paired-domination number of G , denoted by Γ pr (G) , is the maximum cardinality of a minimal paired-dominating set of G. In Upper-PDS , it is required to compute a minimal paired-dominating set with cardinality Γ pr (G) for a given graph G. In this paper, we show that Upper-PDS cannot be approximated within a factor of n 1 − ε for any ε > 0 , unless P = NP and Upper-PDS is APX -complete for bipartite graphs of maximum degree 4. On the positive side, we show that Upper-PDS can be approximated within O (Δ) -factor for graphs with maximum degree Δ. We also show that Upper-PDS is solvable in polynomial time for threshold graphs, chain graphs, and proper interval graphs. [ABSTRACT FROM AUTHOR]

A perfect Roman dominating function on a graph G is a function f : V (G) ⟶ { 0 , 1 , 2 } having the property that for every vertex u with f (u) = 0 , there exists exactly one vertex v such that u v ∈ E (G) and f (v) = 2. The weight of f , denoted by w (f) , is the value ∑ v ∈ V (G) f (v). Given a graph G and a positive integer k , the perfect Roman domination problem is to decide whether there is a perfect Roman dominating function f on G such that w (f) is at most k. In this paper, we first show that the perfect Roman domination problem is NP -complete for chordal graphs, planar graphs, and bipartite graphs. Then we present polynomial time algorithms for computing a perfect Roman dominating function with minimum weight in block graphs, cographs, series-parallel graphs, and proper interval graphs. • We study the perfect Roman domination problem from the algorithmic point of view. • The perfect Roman domination problem is NP -complete for chordal graphs, planar graphs, and bipartite graphs. • We present linear time algorithms for computing the perfect Roman domination number in block graphs, cographs, and series-parallel graphs. • Further, a polynomial time algorithm is proposed for computing the perfect Roman domination number in proper interval graphs. [ABSTRACT FROM AUTHOR]

In this paper, we characterize cubic and quartic Cayley graphs on abelian groups that admit an efficient dominating set, and then we give domination numbers, even when they do not have an efficient dominating set, when it is possible. [ABSTRACT FROM AUTHOR]

A double Roman dominating function (DRDF) on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f (v) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f (w) = 3 , and if f (v) = 1 , then vertex v must have at least one neighbor w with f (w) ≥ 2. The weight of a DRDF is the sum of its function values over all vertices, and the double Roman domination number γ d R (G) is the minimum weight of a DRDF on G. Let G be a connected graph G of order n and minimum degree at least two. With the exception of seven graphs of order at most seven, Beeler et al. (2016) observed that γ d R (G) ≤ 6 n 5 and posed the question whether this bound can be improved. Amjadi et al. (2018) settled this question by proving that γ d R (G) ≤ 8 n 7 . In this paper, we improve this bound to γ d R (G) ≤ 11 n 10 . Moreover, we provide an infinite family of graphs attaining this bound. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies distance-based clique relaxations in unit disk graphs arising in wireless networking applications. Namely, a 2-clique is a subset of nodes with pairwise distance at most two in the graph, and a 2-club is a subset of nodes inducing a subgraph of diameter two. It is shown that in a unit disk graph any 2-clique is 4-dominated and any 2-club is 3-dominated. The former observation is used to develop a -approximation algorithm for the maximum 2-clique problem in unit disk graphs. Moreover, this also implies polynomial solvability of the minimum dominating set problem in unit disk graphs of diameter two, whereas the same problem is shown to be hard in general diameter-two graphs. The paper also poses several related open questions of interest. [Copyright &y& Elsevier]

Abstract: This paper studies a variation of domination in graphs called rainbow domination. For a positive integer , a -rainbow dominating function of a graph is a function such that for any vertex with . The -rainbow domination number of is the minimum value of , where runs over all -rainbow dominating functions of . A related concept is as follows. A weak -dominating function of is a function such that for any vertex with . The weak -domination number of is the minimum value of , where runs over all weak -dominating functions of . In this paper, we prove that for any strongly chordal graph . Our approach is a more general setting called the -function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak -domination numbers of block graphs. [Copyright &y& Elsevier]

In (k , r) - Center we are given a (possibly edge-weighted) graph and are asked to select at most k vertices (centers), so that all other vertices are at distance at most r from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically: • For any r ≥ 1 , we show an algorithm that solves the problem in O ∗ ( (3 r + 1) cw) time, where cw is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithm's performance. As a corollary, for r = 1 , this closes the gap that previously existed on the complexity of Dominating Set parameterized by cw. • We strengthen previously known FPT lower bounds, by showing that (k , r) - Center is W[1]-hard parameterized by the input graph's vertex cover (if edge weights are allowed), or feedback vertex set, even if k is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs. • We show that the complexity of the problem parameterized by tree-depth is 2 Θ (td 2) , by showing an algorithm of this complexity and a tight ETH-based lower bound. We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth, which work efficiently independently of the values of k , r. In particular, we give algorithms which, for any ϵ > 0 , run in time O ∗ ( (tw ∕ ϵ) O (tw) ) , O ∗ ( (cw ∕ ϵ) O (cw) ) and return a (k , (1 + ϵ) r) -center if a (k , r) -center exists, thus circumventing the problem's W-hardness. [ABSTRACT FROM AUTHOR]

A kernel of a digraph, D , is a set of vertices, K , which is both independent: every two vertices are not adjacent; and absorbent: for every vertex in V (D) ∖ K there exists an ex-neighbor in K. A digraph is said to be kernel-perfect if and only if any induced subdigraph has a kernel. A classical result obtained by Sands, Sauer and Woodrow in 1982 asserts that the union of two transitive digraphs is a kernel-perfect digraph. A digraph D is transitive whenever the existence of the arcs (u , v) and (v , w) in D implies the existence of the arc (u , w) in D. Later, it was studied the union of a right-pretransitive digraph and a left-pretransitive digraph, and how it becomes a kernel-perfect digraph (Galeana-Sánchez and Rojas-Monroy, 2004). In this paper we obtain sufficient conditions for the union of two kernel-perfect digraphs becomes a kernel perfect digraph. And these conditions are tight. As a consequence many previous results are generalized. [ABSTRACT FROM AUTHOR]

It is well known that the Cartesian product of two paths, the grid P m □ P n , m ≤ n , has an independent dominating set such that every vertex not in the set has exactly one neighbor in it, if and only if m = n = 4 or m = 2 , n = 2 k + 1. In this paper we prove that every grid P m □ P n has an independent dominating set such that every vertex not in the set has at most two neighbors in it, and we also calculate the minimum cardinality of such sets. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph, a set S ⊆ V is a total k -dominating set if every vertex v ∈ V has at least k neighbors in S. The total k -domination number γ k t (G) is the minimum cardinality among all total k -dominating sets. In this paper, we obtain several tight bounds for the total k -domination number of the strong product of two graphs. In particular, we investigate the relationship between the total k -domination number of the strong product of two graphs with the domination, k -domination and total k -domination numbers of the factors in the product. [ABSTRACT FROM AUTHOR]

Abstract We study the parameterized complexity of domination problems on sparse graphs and beyond. The nowhere dense classes of graphs have been proposed as the main model for sparseness that can be utilized algorithmically. The class of d -degenerate graphs is not nowhere dense, yet domination remains fixed-parameter tractable. Both nowhere dense classes of graphs and d -degenerate graph classes are biclique-free classes, meaning there is an integer t such that no graph in the class contains K t , t as a subgraph. In this paper we show that various domination problems are fixed-parameter tractable on biclique-free classes of graphs. Our algorithms are simple and rely on results from extremal graph theory that bound the number of edges in a t -biclique free graph. In particular, the problems k -Dominating Set , Connected k -Dominating Set , Independent k -Dominating Set and Minimum Weight k -Dominating Set are shown to be FPT, when parameterized by t + k , on graphs not containing K t , t as a subgraph. With the exception of Connected k -Dominating Set all described algorithms are linear in the size of the input graph. [ABSTRACT FROM AUTHOR]

In [Secure domination in proper interval graphs, Discrete Applied Mathematics 247 (2018) 70–76], Araki and Miyazaki proposed a linear-time algorithm for finding the secure domination number of proper interval graphs. However, the example they provided is exactly a counterexample. Based on their main idea, we propose a new simple algorithm for solving this problem in this paper. [ABSTRACT FROM AUTHOR]

A distribution δ of pebbles on a graph G is a mapping of V (G) onto the set N ∪ { 0 }. For each vertex v ∈ V (G) , δ (v) denotes the number of pebbles distributed to v. A pebbling move consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. A distribution of a given graph G is t -solvable if, whenever we choose any target vertex v of G , we can move t pebbles on v by using pebbling moves. The optimal t -pebbling number of the graph G , denoted by π t ∗ (G) , is the minimum number of pebbles needed so that there is a t -solvable distribution of G. A distribution δ of G is called a c -restricted pebbling configuration (abbreviated c -RPC) if δ (v) ≤ c for each v ∈ V (G). The c -restricted optimal t -pebbling number, denoted by π t c (G) , is the minimum number of pebbles needed so that there is a t -solvable c -RPC of G. When t = 1 , we use π c (G) to denote π 1 c (G). In the article titled "Restricted optimal pebbling and domination in graphs", Chellali et al. showed that π 2 (T) ≤ ⌈ 5 n ∕ 7 ⌉ and posed an open problem that characterizes the graphs G for which π 2 (G) = 5. In this paper, we first prove that π 2 (T) ≤ ⌈ 2 n ∕ 3 ⌉ for every tree T of order n. Then, we characterize the graphs G for which π 2 (G) = 5. [ABSTRACT FROM AUTHOR]

Abstract This paper studies a variation of domination in graphs called (F , B , R) -domination. Let G = (V , E) be a graph and V be the disjoint union of F , B , and R , where F consists of free vertices, B consists of bound vertices, and R consists of required vertices. An (F , B , R) -dominating set of G is a subset D ⊆ V such that R ⊆ D and each vertex in B − D is adjacent to some vertex in D. An (F , B , R) -2-stable set of G is a subset S ⊆ B such that S ∩ N (R) = 0̸ and every two distinct vertices x and y in S have distance d (x , y) > 2. We prove that if G is strongly chordal, then α F , B , R , 2 (G) = γ F , B , R (G) − | R | , where γ F , B , R (G) is the minimum cardinality of an (F , B , R) -dominating set of G and α F , B , R , 2 (G) is the maximum cardinality of an (F , B , R) -2-stable set of G. Let D 1 → ∗ D 2 denote D 1 being transferable to D 2. We prove that if G is a connected strongly chordal graph in which D 1 and D 2 are two (F , B , R) -dominating sets with | D 1 | = | D 2 | , then D 1 → ∗ D 2. We also prove that if G is a cactus graph in which D 1 and D 2 are two (F , B , R) -dominating sets with | D 1 | = | D 2 | , then D 1 ∪ { 1 ⋅ extra } → ∗ D 2 ∪ { 1 ⋅ extra } , where ∪ { 1 ⋅ extra } means adding one extra element. [ABSTRACT FROM AUTHOR]

Abstract A double Roman dominating function on a graph G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that every vertex of weight 0 under f has at least one neighbor of weight 3 under f or at least two neighbors of weight 2 under f and every vertex of weight 1 under f has at least one neighbor of weight at least 2 under f. The weight of a double Roman dominating function f is the sum of the weights of the vertices. The double Roman domination number of G , denoted γ dR (G) , is the minimum weight of a double Roman dominating function in G. For every graph G , γ dR (G) ≤ 3 γ (G) , where γ (G) denotes the domination number of G. A graph G satisfying γ dR (G) = 3 γ (G) is a double Roman graph. In this paper, we characterize the double Roman trees, which answers a problem posed by Beeler et al. (2016). [ABSTRACT FROM AUTHOR]

Abstract For a graph G = (V , E) , a set D ⊆ V is called a semitotal dominating set of G if D is a dominating set of G , and every vertex in D is within distance 2 of another vertex of D. The Minimum Semitotal Domination problem is to find a semitotal dominating set of minimum cardinality. Given a graph G and a positive integer k , the Semitotal Domination Decision problem is to decide whether G has a semitotal dominating set of cardinality at most k. The Semitotal Domination Decision problem is known to be NP-complete for general graphs. In this paper, we show that the Semitotal Domination Decision problem remains NP-complete for planar graphs, split graphs and chordal bipartite graphs. We give a polynomial time algorithm to solve the Minimum Semitotal Domination problem in interval graphs. We show that the Minimum Semitotal Domination problem in a graph with maximum degree Δ admits an approximation algorithm that achieves the approximation ratio of 2 + 3 ln ⁡ (Δ + 1) , showing that the problem is in the class log-APX. We also show that the Minimum Semitotal Domination problem cannot be approximated within (1 − ϵ) ln ⁡ | V | for any ϵ > 0 unless NP ⊆ DTIME (| V | O (log ⁡ log ⁡ | V |)). Finally, we prove that the Minimum Semitotal Domination problem is APX-complete for bipartite graphs with maximum degree 4. [ABSTRACT FROM AUTHOR]

Abstract 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 Koh et al. (2013), it is proved that if G is a graph of order n ≥ 4 and δ (G) ≥ 2 , then γ t r (G) ≤ n − n 4 3. It is further conjectured that this bound can be improved to γ t r (G) ≤ n − θ (n). In this paper we show that if G is a graph with no C 3 components and δ (G) ≥ 2 , then γ t r (G) ≤ n − n 2 . [ABSTRACT FROM AUTHOR]

Abstract A set D ⊆ V of a graph G = (V , E) is called a dominating set of G if every vertex in V ∖ D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if G [ D ] , the subgraph of G induced by D , has a perfect matching. Given a graph G , Min-Paired-Dom-Set is the problem to find a paired-dominating set of G of minimum cardinality. Min-Paired-Dom-Set is known to be NP -hard for general graphs and many other restricted classes of graphs. However, Min-Paired-Dom-Set is solvable in polynomial time in some graph classes including strongly chordal graphs and chordal bipartite graphs. In this paper, we strengthen this result by proposing a polynomial time algorithm to compute a minimum paired-dominating set in the class of strongly orderable graphs, which includes strongly chordal graphs and chordal bipartite graphs. The algorithm runs in linear time if a quasi-simple elimination ordering of the strongly orderable graph is provided. [ABSTRACT FROM AUTHOR]

Abstract A set D ⊆ V is called a dominating set of G = (V , E) if | N G [ v ] ∩ D | ≥ 1 for all v ∈ V. The Minimum Domination problem is to find a dominating set of minimum cardinality of the input graph. In this paper, we study the Minimum Domination problem for star-convex bipartite graphs, circular-convex bipartite graphs and triad-convex bipartite graphs. It is known that the Minimum Domination Problem for a graph with n vertices can be approximated with an approximation ratio of ln n + 1. However, we show that for any ϵ > 0 , the Minimum Domination problem does not admit a (1 − ϵ) ln n -approximation algorithm even for star-convex bipartite graphs with n vertices unless NP ⊆ DTIME (n O (log log n) ). On the positive side, we propose polynomial time algorithms for computing a minimum dominating set of circular-convex bipartite graphs and triad-convex bipartite graphs, by making polynomial time Turing reductions from the Minimum Domination problem for these graph classes to the Minimum Domination problem for convex bipartite graphs. [ABSTRACT FROM AUTHOR]

Abstract A matching in a hypergraph H is a set of pairwise disjoint hyperedges. The matching number α ′ (H) of H is the size of a maximum matching in H. A subset D of vertices of H is a dominating set of H if for every v ∈ V ∖ D there exists u ∈ D such that u and v lie in a hyperedge of H. The cardinality of a minimum dominating set of H is called the domination number of H , denoted by γ (H). It is known that for an intersecting hypergraph H with rank r , γ (H) ≤ r − 1. In this paper we present structural properties on intersecting hypergraphs with rank r satisfying the equality γ (H) = r − 1. By applying these properties we show that all linear intersecting hypergraphs H with rank 4 satisfying γ (H) = r − 1 can be constructed by the well-known Fano plane. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies a variation of domination in graphs called rainbow domination. For a positive integer , a -rainbow dominating function of a graph is a function from to the set of all subsets of such that for any vertex with we have . The -rainbow domination is the same as the ordinary domination. The -rainbow domination problem is to determine the -rainbow domination number of a graph , that is the minimum value of where runs over all -rainbow dominating functions of . In this paper, we prove that the -rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the -rainbow domination problem on trees. For a given tree , we also determine the smallest such that . [Copyright &y& Elsevier]

A graph G is said to be k–γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k−1 vertices. The structure of k–γ-critical graphs remains far from completely understood, even in the special case when the domination number γ=3. In a 1983 paper, Sumner and Blitch proved a theorem which may regarded as a result related to the toughness of 3-γ-critical graphs which says that if S is any vertex cutset of such a graph, then G−S has at most |S|+1 components. In the present paper, we improve and extend this result considerably. [Copyright &y& Elsevier]

A matching in a hypergraph H is a set of pairwise disjoint hyperedges. The matching number ν ( H ) of H is the size of a maximum matching in H . A subset D of vertices of H is a dominating set of H if for every v ∈ V ∖ D there exists u ∈ D such that u and v lie in an hyperedge of H . The cardinality of a minimum dominating set of H is the domination number of H , denoted by γ ( H ) . It was proved that γ ( H ) ≤ ( r − 1 ) ν ( H ) for r -uniform hypergraphs and the 2-uniform hypergraphs (graphs) achieving equality γ ( H ) = ν ( H ) have been characterized. In this paper we generalize the inequality γ ( H ) ≤ ( r − 1 ) ν ( H ) to arbitrary hypergraph of rank r and we completely characterize the extremal hypergraphs H of rank 3 achieving equality γ ( H ) = ( r − 1 ) ν ( H ) . [ABSTRACT FROM AUTHOR]

Based on the history that the Emperor Constantine decreed that any undefended place (with no legions) of the Roman Empire must be protected by a “stronger” neighbor place (having two legions), a graph theoretical model called Roman domination in graphs was described. A Roman dominating function for a graph G = ( V , E ) , is a function f : V → { 0 , 1 , 2 } such that every vertex v with f ( v ) = 0 has at least a neighbor w in G for which f ( w ) = 2 . The Roman domination number of a graph is the minimum weight, ∑ v ∈ V f ( v ) , of a Roman dominating function. In this paper we initiate the study of a new parameter related to Roman domination, which we call strong Roman domination number and denote it by γ S t R ( G ) . We approach the problem of a Roman domination-type defensive strategy under multiple simultaneous attacks and begin with the study of several mathematical properties of this invariant. In particular, we first show that the decision problem regarding the computation of the strong Roman domination number is NP-complete, even when restricted to bipartite graphs. We obtain several bounds on such a parameter and give some realizability results for it. Moreover, we prove that for any tree T of order n ≥ 3 , γ S t R ( T ) ≤ 6 n / 7 and characterize all extremal trees. [ABSTRACT FROM AUTHOR]

Let γ ( G ) and ι ( G ) be the domination and independent domination numbers of a graph G , respectively. Introduced by Sumner and Moore (1979), a graph G is domination perfect if γ ( H ) = ι ( H ) for every induced subgraph H ⊆ G . In 1991, Zverovich and Zverovich proposed a characterization of domination perfect graphs in terms of forbidden induced subgraphs. Fulman (1993) noticed that this characterization is not correct. Later, Zverovich and Zverovich (1995) offered such a second characterization with 17 forbidden induced subgraphs. However, the latter still needs to be adjusted. In this paper, we point out a counterexample. We then give a new characterization of domination perfect graphs in terms of only 8 forbidden induced subgraphs and a short proof thereof. Moreover, in the class of domination perfect graphs, we propose a polynomial-time algorithm computing, given a dominating set D , an independent dominating set Y such that | Y | ≤ ∣ D ∣ . [ABSTRACT FROM AUTHOR]

A set D ⊆ V of a graph G = ( V , E ) is called an open neighborhood locating–dominating set (OLD-set) if (i) N G ( v ) ∩ D ≠ 0̸ for all v ∈ V , and (ii) N G ( u ) ∩ D ≠ N G ( v ) ∩ D for every pair of distinct vertices u , v ∈ V . Given a graph G = ( V , E ) , the Min OLD-set problem is to find an OLD-set of minimum cardinality. Given a graph G = ( V , E ) and a positive integer k , the Decide OLD-set problem is to decide whether G has an OLD-set of cardinality at most k . The Decide OLD-set problem is known to NP-complete for general graphs. In this paper we extend the NP-completeness result of the Decide OLD-set problem by showing that it remains NP-complete for bipartite graphs, planar graphs, split graphs and doubly chordal graphs. We prove that the Decide OLD-set problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for the Min OLD-set problem in trees. We also propose a ( 2 + 3 ln Δ ) -approximation algorithm for the Min OLD-set problem and show that the Min OLD-set problem cannot be approximated within 1 2 ( 1 − ϵ ) ln | V | for any ϵ > 0 unless NP ⊆ DTIME ( | V | O ( log log | V | ) ) . Finally, we prove that the Min OLD-set problem is APX-complete for bipartite graphs of maximum degree 3. [ABSTRACT FROM AUTHOR]

For any two vertices u and v in a graph G , d G ( u , v ) denote the distance between u and v in G . The square of a graph G = ( V , E ) is the graph G 2 = ( V , E 2 ) such that u v ∈ E 2 if and only if d G ( u , v ) ∈ { 1 , 2 } . An efficient dominating set (e.d. for short) in G is a subset D of vertices such that D is an independent set and each vertex outside D has exactly one neighbor in D . In general, (i) if P is a (hereditary) graph property, and if a graph G satisfies P , then G 2 does not need to satisfy P , and (ii) if H is any graph, and if G is a H -free graph that has an e.d., then G 2 need not be H -free. In this paper, we show that the squares of ( P 6 , banner)-free graphs that have an e.d. are again ( P 6 , banner)-free. This result together with some known results implies that the Efficient Dominating Set problem (which asks for the existence of an e.d. in a given graph G ) can be solved in time O ( n 3 ) for ( P 6 , banner)-free graphs. Here, P t denotes the chordless path on t vertices, and a banner is the graph obtained from a chordless cycle on four vertices by adding a vertex that has exactly one neighbor on the cycle. [ABSTRACT FROM AUTHOR]

A function f : V → { − 1 , 0 , 1 } is a minus-domination function of a graph G = ( V , E ) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f ( x ) over all vertices x ∈ V . In the minus-domination problem, one tries to minimize the weight of a minus-domination function. In this paper, we show that (1) the minus-domination problem is fixed-parameter tractable for d -degenerate graphs when parameterized by the size of the minus-dominating set and by d , where the size of a minus domination is the number of vertices that are assigned 1 , (2) the minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs, (3) it is N P -complete for split graphs, and (4) there is no fixed-parameter algorithm for minus-domination. [ABSTRACT FROM AUTHOR]

A subset D ⊆ V of a graph G = ( V , E ) is a ( 1 , j ) -set (Chellali et al., 2013) if every vertex v ∈ V ∖ D is adjacent to at least 1 but not more than j vertices in D . The cardinality of a minimum ( 1 , j ) -set of G , denoted as γ ( 1 , j ) ( G ) , is called the ( 1 , j ) -domination number of G . In this paper, using probabilistic methods, we obtain an upper bound on γ ( 1 , j ) ( G ) for j ≥ O ( log Δ ) , where Δ is the maximum degree of the graph. The proof of this upper bound yields a randomized linear time algorithm. We show that the associated decision problem is NP-complete for choral graphs but, answering a question of Chellali et al., provide a linear-time algorithm for trees for a fixed j . Apart from this, we design a polynomial time algorithm for finding γ ( 1 , j ) ( G ) for a fixed j in a split graph, and show that ( 1 , j ) -set problem is fixed parameter tractable in bounded genus graphs and bounded treewidth graphs. [ABSTRACT FROM AUTHOR]

In 1996, Tarjan and Matheson proved that if G is a plane triangulated disc with n vertices, γ ( G ) ≤ n / 3 , where γ ( G ) denotes the domination number of G , i.e. the cardinality of the smallest set of vertices S such that every vertex of G is either in S or adjacent to a vertex in S . Furthermore, they conjectured that the constant 1 / 3 could be improved to 1 / 4 for a sufficiently large n . Their conjecture remains unsettled. In the present paper, it is proved that if G is a Hamiltonian plane triangulation with n vertices and minimum degree at least 4, then γ ( G ) ≤ max { ⌈ 2 n / 7 ⌉ , ⌊ 5 n / 16 ⌋ } . It follows immediately that if G is a 4-connected plane triangulation with n vertices, then γ ( G ) ≤ max { ⌈ 2 n / 7 ⌉ , ⌊ 5 n / 16 ⌋ } . [ABSTRACT FROM AUTHOR]

A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V ( D ) ∖ N there exists an arc from w to N . The digraph D is said to be a kernel-perfect digraph when every induced subdigraph of D has a kernel. Minimal non kernel-perfect digraphs are called critical kernel-imperfect digraphs. The broader sufficient condition for the existence of kernels in digraphs known so far is that states: (1) If D is a digraph such that every odd cycle has two consecutive poles, then D is kernel-perfect. In this paper is studied the structure of critical kernel-imperfect digraphs which belong to a very large special classes of digraphs and many structural properties are obtained. As a consequence ( 1 ) is widely generalized in this class of digraphs, where the condition of the poles is requested only for odd cycles whose edges alternate in a set of arcs. As consequence, some classic results of kernel-perfect and finite critical kernel-imperfect digraphs are generalized for these classes of digraphs. [ABSTRACT FROM AUTHOR]

A set D ⊆ V is called a total dominating set of a graph G = ( V , E ) , if for all v ∈ V , | N G ( v ) ∩ D | ≥ 1 . A total dominating set D of G = ( V , E ) is called a total outer-connected dominating set if G [ V ∖ D ] is connected. The Minimum Total Outer-connected Domination problem for a graph G = ( V , E ) is to find a total outer-connected dominating set of minimum cardinality. The Total Outer-connected Domination Decision problem, the decision version of the Minimum Total Outer-connected Domination problem, is known to be NP-complete for general graphs. In this paper, we strengthen this NP-completeness result by showing that the Total Outer-connected Domination Decision problem remains NP-complete for chordal graphs, split graphs, and doubly chordal graphs. We prove that the Total Outer-connected Domination Decision problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for computing the total outer-connected domination number, the cardinality of a minimum total outer-connected dominating set, of a tree. We prove that the Minimum Total Outer-connected Domination problem cannot be approximated within a factor of ( 1 − ε ) ln | V | for any ε > 0 , unless NP ⊆ DTIME ( | V | O ( log log | V | ) ) . Finally, we show that the Minimum Total Outer-connected Domination problem is APX-complete for bounded degree graphs. [ABSTRACT FROM AUTHOR]

In this paper we give a characterization of triangulations where all minimal dominating sets have the same cardinality and a characterization of triangulations where all six domination parameters are the same. [ABSTRACT FROM AUTHOR]

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S . The domination number, γ ( G ) , of G is the minimum cardinality of a dominating set of G . A set S of vertices in G is a disjunctive dominating set in G if every vertex not in S is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it in G . The disjunctive domination number, γ 2 d ( G ) , of G is the minimum cardinality of a disjunctive dominating set in G . It is known that there exist graphs G that belong to the class of bipartite graphs or claw-free graphs or chordal graphs such that γ ( G ) > C γ 2 d ( G ) for any given constant C . In this paper, we show that if T is a tree, then γ ( T ) ≤ 2 γ 2 d ( T ) − 1 , and we provide a constructive characterization of the trees achieving equality in this bound. [ABSTRACT FROM AUTHOR]

In this paper we introduce the notion of distance k-guarding applied to triangulation graphs, and associate it with distance k-domination and distance k-covering. We obtain results for maximal outerplanar graphs when k=2. A set S of vertices in a triangulation graph T is a distance 2-guarding set (or 2d-guarding set for short) if every face of T has a vertex adjacent to a vertex of S. We show that ... (respectively, ...) vertices are sufficient to 2d-guard and 2d-dominate (respectively, 2d-cover) any n-vertex maximal outerplanar graph. We also show that these bounds are tight. [ABSTRACT FROM AUTHOR]

In the first part of this paper, we investigate the interdependence of the connected domination number γ c ( G ) and the domination number γ ( G ) in some hereditary graph classes. We prove the following results: • A connected graph G is ( P 6 , C 6 ) -free if and only if γ c ( H ) ⩽ γ ( H ) + 1 for every connected induced subgraph H of G . Moreover, there are ( P 6 , C 6 ) -free graphs with arbitrarily large domination number attaining this bound. • For every connected ( P 8 , C 8 ) -free graph G , it holds that γ c ( G ) / γ ( G ) ⩽ 2 , and this bound is attained by connected ( P 7 , C 7 ) -free graphs with arbitrarily large domination number. In particular, the bound γ c ( G ) ⩽ 2 γ ( G ) is best possible even in the class of connected ( P 7 , C 7 ) -free graphs. • The general upper bound of γ c ( G ) / γ ( G ) < 3 is asymptotically sharp on connected ( P 9 , C 9 ) -free graphs. In the second part, we prove that the following decision problem is Θ 2 p -complete, for every fixed rational 1 < r < 3 : given a graph G , is γ c ( G ) / γ ( G ) ⩽ r ? Loosely speaking, this means that deciding whether the ratio of γ c ( G ) and γ ( G ) is bounded by some rational number r with 1 < r < 3 is as hard as computing both γ c ( G ) and γ ( G ) explicitly. [ABSTRACT FROM AUTHOR]

Abstract: The domination number and the total domination number of a graph without an isolated vertex are among the most well-studied parameters in graph theory. While the inequality is an almost immediate consequence of the definition, the extremal graphs for this inequality are not well understood. Furthermore, even very strong additional assumptions do not allow us to improve the inequality by much. In the present paper we consider the relation of and for cubic graphs of large girth. Clearly, in this case is at least where is the order of . If is close to , then this forces a certain structure within . We exploit this structure and prove an upper bound on , which depends on the value of . As a consequence, we can considerably improve the inequality for cubic graphs of large girth. [Copyright &y& Elsevier]

Abstract: In this paper we prove that . This, together with the result of Stȩpień and Zwierzchowski (2014), gives . Since for we have (see Klavžar and Seifter (1995)), it follows that a product is an example of a graph class for which . Moreover, is an example of a graph class for which , where is a weak {2}-domination number introduced in Brešar et al. (2008). [Copyright &y& Elsevier]

Abstract: Let be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters, namely the domination number, , and the total domination number, . A set of vertices in is a semitotal dominating set of if it is a dominating set of and every vertex in is within distance 2 of another vertex of . The semitotal domination number, , is the minimum cardinality of a semitotal dominating set of . We observe that . It is known that , where denotes the matching number of . However, the total domination number and the matching number of a graph are generally incomparable. We provide a characterization of minimal semitotal dominating sets in graphs. Using this characterization, we prove that if is a connected graph on at least two vertices, then and we characterize the graphs achieving equality in the bound. [Copyright &y& Elsevier]

Abstract: Let be a graph. A subset is a dominating set if every vertex not in D is adjacent to a vertex in D. The domination number of G, denoted by , is the smallest cardinality of a dominating set of G. The bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with domination number larger than . The reinforcement number of G is the smallest number of edges whose addition to G results in a graph with smaller domination number than . In 2012, Hu and Xu proved that the decision problems for the bondage, the total bondage, the reinforcement and the total reinforcement numbers are all NP-hard in general graphs. In this paper, we improve these results to bipartite graphs. [Copyright &y& Elsevier]

Abstract: A subset in a graph is a -set if, for every vertex , for non-negative integers and , that is, every vertex is adjacent to at least but not more than vertices in . In this paper, we focus on small and , and relate the concept of -sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and -dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph , the restrained domination number is equal to the domination number of . [Copyright &y& Elsevier]

Abstract: In this paper, we continue the study of neighborhood total domination in graphs first studied by Arumugam and Sivagnanam [S. Arumugam, C. Sivagnanam, Neighborhood total domination in graphs, Opuscula Math. 31 (2011) 519–531]. A neighborhood total dominating set, abbreviated NTD-set, in a graph is a dominating set in with the property that the subgraph induced by the open neighborhood of the set has no isolated vertex. The neighborhood total domination number, denoted by , is the minimum cardinality of a NTD-set of . Every total dominating set is a NTD-set, implying that , where and denote the domination and total domination numbers of , respectively. We show that if is a connected graph on vertices, then and we characterize the graphs achieving equality in this bound. [Copyright &y& Elsevier]

Abstract: Let be a function that assigns to each vertex a subset of colors chosen from a set of colors. If for each vertex with , then is called a -rainbow dominating function ( RDF) of where . The weight of , denoted by , is defined as . Given a graph , the minimum weight among all weights of RDFs, denoted by , is called the -rainbow domination number of . Bres˘ar and S˘umenjak (2007) [5] gave an upper bound and a lower bound for . They showed that . In this paper, we propose a tight upper bound for when . [Copyright &y& Elsevier]

Abstract: An -identifying code in a graph is a subset such that for each the intersection of and the ball of radius centered at is nonempty and unique. Previously, -identifying codes have been studied in various grids. In particular, it has been shown that there exists a -identifying code in the square grid with density and that there are no -identifying codes with density smaller than . Recently, the lower bound has been improved to by Martin and Stanton (2010) [11]. In this paper, we further improve the lower bound by showing that there are no -identifying codes in the square grid with density smaller than . [Copyright &y& Elsevier]