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)?.     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

Stability,domination and irredundance in a graph

In a graph G, a set X is called a stable set if any two vertices of X are nonadjacent. A set X is called a dominating set if every vertex of V – X is joined to at least one vertex of X. A set X is called an irredundant set if every vertex of X, not isolated in X, has at least one proper neighbor, that is a vertex of V – X joined to it but to no other vertex of X. Let α′ and α, γ, and Γ, ir and IR, denote respectively the minimum and maximum cardinalities of a maximal stable set, a minimal dominating set, and a maximal irredundant set. It is known that ir ? γ ? α′ ? α ? Γ ? IR and that if G does not contain any induced subgraph isomorphic to K_1,3, then γ = α′. Here we prove that if G contains no induced subgraph isomorphic to K_1,3 or to the graph H of figure 1, then ir = γ = α′. We prove also that if G contains no induced subgraph isomorphic to K_1,3, to H, or to the graph h of figure 3, then Γ = IR. Finally, we improve a result of Bollobas and Cockayne about sufficient conditions for γ = ir in terms of forbidden subgraphs.     

Proof of a conjecture on irredundance perfect graphs

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002     

Irredundance in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained by replacing every vertex of degree d of G by a clique K_d. We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if γ denotes the domination number of a graph, γ(G_I) − ir(G_I) can be arbitrarily large, IR(G_I) ≤ m(G) and IR(G_I) ≤ n²(G)/4. These results disprove a conjecture of Dunbar and Haynes (Congr. Num. 118 (1996), 143–154) and answer another open question. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 97–104, 1998     

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.     

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.     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.     

On the Ratio Between 2-Domination and Total Outer-Independent Domination Numbers of Trees

A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D.A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D,and the set V(G)\D is independent.The 2-domination(total outer-independent domination,respectively)number of a graph G is the minimum cardinality of a 2-dominating(total outer-independent dominating,respectively)set of G.We investigate the ratio between2-domination and total outer-independent domination numbers of trees.     

Roman and Total Domination

Abstract

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination number ^γt(G). A Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑_{u ∈ V (G)} f (u) over all such functions is called the Roman domination number γR (G). We show that γt(G) ≤ γR (G) with equality if and only if ^γt(G)=2γ(G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.     

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.     

Vertex criticality for upper domination and irredundance

Let π be any of the domination parameters ir γ, i, β, Γ or IR. The graph G is π‐critical (π⁺‐critical) if the removal of any vertex of G causes π(G) to decrease (increase). We show that the classes of IR‐critical and Γ‐critical graphs coincide, and exhibit a class of Γ⁺‐critical graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 205–212, 2001     

Outer-2-independent domination in graphs

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)?D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)?D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

The ratio of the irredundance number and the domination number for block-cactus graphs

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43–56] and Bollobás and Cockayne [J. Graph Theory (1979) 241–249] proved independently that γ(G) < 2ir(G) for any graph G. For a tree T, Damaschke [Discrete Math. (1991) 101–104] obtained the sharper estimation 2γ(T) < 3ir(T). Extending Damaschke's result, Volkmann [Discrete Math. (1998) 221–228] proved that 2γ(G) ≤ 3ir(G) for any block graph G and for any graph G with cyclomatic number μ(G) ≤ 2. Volkmann also conjectured that 5γ(G) < 8ir(G) for any cactus graph. In this article we show that if G is a block-cactus graph having π(G) induced cycles of length 2 (mod 4), then γ(G)(5π(G) + 4) ≤ ir(G)(8π(G) + 6). This result implies the inequality 5γ(G) < 8ir(G) for a block-cactus graph G, thus proving the above conjecture. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 139–149, 1998     

On graphs with equal domination and 2-domination numbers

Let G be a simple graph, and let p be a positive integer. A subset D⊆V(G) is a p-dominating set of the graph G, if every vertex v∈V(G)-D is adjacent to at least p vertices in D. The p-domination numberγ_p(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number γ₁(G) is the usual domination numberγ(G). This definition immediately leads to the inequality γ(G)?γ₂(G).In this paper we present some sufficient as well as some necessary conditions for graphs G with the property that γ₂(G)=γ(G). In particular, we characterize all cactus graphs H with γ₂(H)=γ(H).     

On irredundant Ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the smallest p such that in every two-coloring of the edges of K_p using colors red (R) and blue (B), either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We develop techniques to obtain upper bounds for irredundant Ramsey numbers of the form s(3, n) and prove that 18 ≤ s(3,7) ≤ 19.     

On equality in an upper bound for domination parameters of graphs

We consider the well-known upper bounds μ(G) ≤|V(G)| − Δ(G), where Δ(G) denotes the maximum degree of G and μ(G) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of graphs for which equality does or does not hold and show that the difference between the domination and irredundance numbers can be arbitrary even when equality in the above bound holds for the domination number. © 1997 John Wiley & Sons, Inc.     

Global italian domination in graphs

Abstract

An Italian dominating function (IDF) on a graph G = (V, E) is a function f: V → {0, 1, 2} satisfying the condition that for every vertex v ∈ V (G) with f (v) = 0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to at least two vertices assigned 1. The weight of an IDF f is the value ∑_v∈V(G) f (v). The Italian domination number of a graph G, denoted by γ_I (G), is the minimum weight of an IDF on G. An IDF f on G is called a global Italian dominating function (GIDF) on G if f is also an IDF on the complement ? of G. The global Italian domination number of G, denoted by γ_gI (G), is the minimum weight of a GIDF on G. In this paper, we initiate the study of the global Italian domination number and we present some strict bounds for the global Italian domination number. In particular, we prove that for any tree T of order n ≥ 4, γ_gI (T) ≤ γ_I (T) + 2 and we characterize all trees with γ_gI (T) = γ_I (T) + 2 and γ_gI (T) = γ_I (T) + 1.     

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.