Domination versus disjunctive domination in graphs

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 of G is the minimum cardinality of a dominating set of G. For a positive integer b, a set S of vertices in a graph G is a b-disjunctive dominating set in G if every vertex v not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it in G. The b-disjunctive domination number of G is the minimum cardinality of a b-disjunctive dominating set. In this paper, we continue the study of disjunctive domination in graphs. We present properties of b-disjunctive dominating sets in a graph. A characterization of minimal b-disjunctive dominating sets is given. We obtain bounds on the ratio of the domination number and the b-disjunctive domination number for various families of graphs, including regular graphs and trees.     

Graph-theoretic parameters concerning domination,independence, and irredundance

A vertex x in a subset X of vertices of an undericted graph is redundant if its closed neighbourhood is contained in the union of closed neighborhoods of vertices of X – {x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X – {x}. The irredundance number ir (G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. The domination number γ(G) is the minimum cardinality taken over all dominating sets of G, and the independent domination number i(G) is the minimum cardinality taken over all maximal independent sets of vertices of G. The paper contians results that relate these parameters. For example, we prove that for any graph G, ir (G) > γ(G)/2 and for any grpah Gwith p vertices and no isolated vertices, i(G) ≤ p-γ(G) + 1 - ?(p - γ(G))/γ(G)?.     

Partitioning the Vertices of a Graph into Two Total Dominating Sets

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 of S. We study graphs whose vertex set can be partitioned into two total dominating sets. In particular, we develop several sufficient conditions for a graph to have a vertex partition into two total dominating sets. We also show that with the exception of the cycle on five vertices, every selfcomplementary graph with minimum degree at least two has such a partition.     

Maximal independent sets in minimum colorings

Every graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set (equivalently, a dominating set) in G. Among all such minimum vertex-colorings of the vertices of G, a coloring with the maximum number of color classes that are dominating sets in G is called a dominating-χ-coloring of G. The number of color classes that are dominating sets in a dominating-χ-coloring of G is defined to be the dominating-χ-color number of G. In this paper, we continue to investigate the dominating-χ-color number of a graph first defined and studied in [1].     

On Trees with Double Domination Number Equal to the 2-Outer-Independent Domination Number Plus One

A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.     

A characterization of (γ, i)‐trees

We characterize trees with equal domination and independent domination numbers in terms of the sets of vertices of the tree which are contained in all its minimum dominating and minimum independent dominating sets. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 277–292, 2000     

Steiner centers in graphs

The Steiner distance of a set S of vertices in a connected graph G is the minimum size among all connected subgraphs of G containing S. For n ≥ 2, the n-eccentricity e_n(ν) of a vertex ν of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contains ν. The n-diameter of G is the maximum n-eccentricity among the vertices of G while the n-radius of G is the minimum n-eccentricity. The n-center of G is the subgraph induced by those vertices of G having minimum n-eccentricity. It is shown that every graph is the n-center of some graph. Several results on the n-center of a tree are established. In particular, it is shown that the n-center of a tree is a tree and those trees that are n-centers of trees are characterized.     

Contributions to the theory of domination,independence and irredundance in graphs

A vertex x in a subset X of vertices of an undirected graph is redundant if its closed neighbourhood is contained in the union of closed neighbourhoods of vertices of X?{x}. In the context of a communications network, this means that any vertex which may receive communications from X may also be informed from X?{x}. The lower and upper irredundance numbers ir(G) and IR(G) are respectively the minimum and maximum cardinalities taken over all maximal sets of vertices having no redundancies. The domination number γ(G) and upper domination number Γ(G) are respectively the minimum and maximum cardinalities taken over all minimal dominating sets of G. The independent domination number i(G) and the independence number β(G) are respectively the minimum and maximum cardinalities taken over all maximal independent sets of vertices of G.A variety of inequalities involving these quantities are established and sufficient conditions for the equality of the three upper parameters are given. In particular a conjecture of Hoyler and Cockayne [9], namely $\text{i+β?2p + 2δ - 2}\text{2pδ}$, is proved.     

Vertices contained in all minimum paired-dominating sets of a tree

A set S of vertices in a graph G is called a paired-dominating set if it dominates V and 〈S〉 contains at least one perfect matching. We characterize the set of vertices of a tree that are contained in all minimum paired-dominating sets of the tree.     

Bounds on global secure sets in cactus trees

Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances.     

Bounds on the <Emphasis Type="Italic">k</Emphasis>-tuple domatic number of a graph

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A vertex of a graph G dominates itself and all vertices adjacent to it. A subset S ⊆ V (G) is a k-tuple dominating set of G if each vertex of V (G) is dominated by at least k vertices in S. The k-tuple domatic number of G is the largest number of sets in a partition of V (G) into k-tuple dominating sets.     

Randomized greedy algorithms for finding small k‐dominating sets of regular graphs

A k‐dominating set of a graph G is a subset ?? of the vertices of G such that every vertex of G is either in ?? or at distance at most k from a vertex in ??. It is of interest to find k‐dominating sets of small cardinality. In this paper we consider simple randomized greedy algorithms for finding small k‐dominating sets of regular graphs. We analyze the average‐case performance of the most efficient of these simple heuristics showing that it performs surprisingly well on average. The analysis is performed on random regular graphs using differential equations. This, in turn, proves upper bounds on the size of a minimum k‐dominating set of random regular graphs. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 22, 2005     

Locating and total dominating sets in trees

A set S of vertices in a graph G=(V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. We consider total dominating sets of minimum cardinality which have the additional property that distinct vertices of V are totally dominated by distinct subsets of the total dominating set.     

Dominating cliques in P5-free graphs

All induced connected subgraphs of a graphG contain a dominating set of pair-wise adjacent vertices if and only if there is no induced subgraph isomorphic to a path or a cycle of five vertices inG. Moreover, the problem of finding any given type of connected dominating sets in all members of a classG of graphs can be reduced to the graphsG∈G that have a cut-vertex or do not contain any cutsetS dominated by somes∈S. This research was supported in part by the “AKA” Research Fund of the Hungarian Academy of Sciences.     

Disjoint independent dominating sets in graphs

A set X of vertices of G is an independent dominating set if no two vertices of X are adjacent and each vertex not in X is adjacent to at least one vertex in X. Independent dominating sets of G are cliques of the complement $\text{G}$ of G and conversely.This work is concerned with the existence of disjoint independent dominating sets in a graph G. A new parameter, the maximum number of disjoint independent dominating sets in G, is studied and the class of graphs whose vertex sets partition into independent dominating sets is investigated.     

Connected -tuple twin domination in de Bruijn and Kautz digraphs

For a digraph G, a k-tuple twin dominating set D of G for some fixed k≥1 is a set of vertices such that every vertex is adjacent to at least k vertices in D, and also every vertex is adjacent from at least k vertices in D. If the subgraph of G induced by D is strongly connected, then D is called a connected k-tuple twin dominating set of G. In this paper, we give constructions of minimal connected k-tuple twin dominating sets for de Bruijn digraphs and Kautz digraphs.     

A linear algorithm for the domination number of a series-parallel graph

A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph.     

Bounds on cost effective domination numbers

A vertex υ in a set S is said to be cost effective if it is adjacent to at least as many vertices in V\S as it is in S and is very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is (very) cost effective if every vertex in S is (very) cost effective. The minimum cardinality of a (very) cost effective dominating set of G is the (very) cost effective domination number of G. Our main results include a quadratic upper bound on the very cost effective domination number of a graph in terms of its domination number. The proof of this result gives a linear upper bound for hereditarily sparse graphs which include trees. We show that no such linear bound exists for graphs in general, even when restricted to bipartite graphs. Further, we characterize the extremal trees attaining the bound. Noting that the very cost effective domination number is bounded below by the domination number, we show that every value of the very cost effective domination number between these lower and upper bounds for trees is realizable. Similar results are given for the cost effective domination number.     

Reviewing some Results on Fair Domination in Graphs

A fair dominating set in a graph G is a dominating set S such that all vertices not in S are dominated by the same number of vertices from S; that is, every two vertices outside S have the same number of neighbors in S. The fair domination number fd(G) of G is the minimum cardinality of a fair dominating set. In this work, we review the results stated in [Caro, Y., Hansberg, A., and Henning, M., Fair domination in graphs, Discrete Math. 312 (2012), no. 19, 2905–2914], where the concept of fair domination was introduced. Also, some bounds on the fair domination number are derived from results obtained in [Caro, Y., Hansberg, A., and Pepper, R., Regular independent sets in graphs, preprint].     

Bounds on Laplacian eigenvalues related to total and signed domination of graphs

A total dominating set in a graph G is a subset X of V (G) such that each vertex of V (G) is adjacent to at least one vertex of X. The total domination number of G is the minimum cardinality of a total dominating set. A function f: V (G) → {−1, 1} is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of G is the minimum weight of an SDF on G. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph in terms of the signed domination number of the graph.