# Graphs with Constant Sum of Domination and Inverse Domination Numbers

Authors: T. Tamizh Chelvam; T. Asir
Journal: International Journal of Combinatorics
 (2012)

---

## Abstract

A subsetD of the vertex set of a graph G, is a dominating set if every vertex in V−D is adjacent to at least one vertex in D. The domination number γ(G) is the minimum cardinality of a dominating set of G. A subset of V−D, which is also a dominating set of G is called an inverse dominating set of G with respect to D. The inverse domination number γ′(G) is the minimum cardinality of the inverse dominating sets. Domke et al. (2004) characterized connected graphs G with γ(G)+γ′(G)=n, where n is the number of vertices in G. It is the purpose of this paper to give a complete characterization of graphs G with minimum degree at least two and γ(G)+γ′(G)=n−1.


---

## Body

## 1. Introduction

LetG=(V,E) be a simple graph. For D⊆V, if every vertex in V-D is adjacent to at least one vertex in D, then D is said to be a dominating set of G [1].A dominating set D is said to be a minimal dominating set if no proper subset of D is a dominating set of G. The minimum cardinality among all dominating sets of G is called domination number of G, and it is denoted by γ(G). Any dominating set of G with cardinality γ(G) is noted as a γ set of G [1]. Let D be a γ-set of G. If V-D contains a dominating set D' of G, then D' is called an inverse dominating set with respect to D. The minimum cardinality of all inverse dominating sets is called the inverse domination number [2] and is denoted by γ'(G). An inverse dominating set D' is called a γ′-set if |D′|=γ′. By virtue of the definition of the inverse domination number, γ(G)≤γ′(G). The concept of the inverse domination number was introduced by Kulli and Sigarkanti [2]. It is well known by Ore’s Theorem [3] that if a graph G has no isolated vertices, then the complement V-D of every γ-set D contains a dominating set. Thus any graph with no isolated vertices contains an inverse dominating set. However, for graphs with isolated vertices, one cannot find an inverse dominating set. For this reason, hereafter, we restrict ourselves to graphs with no isolated vertices.A Gallai-type theorem has the formα(G)+β(G)=n, where α(G) and β(G) are parameters defined on the graph G, and n is the number of vertices in G. Cockayne et al. [4] proved certain Gallai-type theorems for graphs. In the year 1996, Cockayne et al. characterized graphs with δ(G)≥2 and γ(G)=⌊n/2⌋. Since then Baogen et al. [5] and Randerath and Volkmann [6] independently characterized all graphs G satisfying γ(G)=⌊n/2⌋. Next in the year  2004,  Domke et al. [7] characterized graphs for which γ(G)+γ′(G)=n. Later on, in the year 2010, Tamizh Chelvam and Grace Prema [8] characterized graphs with γ(G)=γ′(G)=(n-1)/2 where n is an odd positive integer. Now, in this paper we characterize all graphs G with δ(G)≥2 for which γ(G)+γ′(G)=n-1.Motivated by the inverse domination number, Hedetniemi et al. [9] defined and studied the disjoint domination number γγ(G) of a graph G. A pair (D1,D2) of disjoint sets of vertices D1,D2⊆V is said to dominate a vertex u∈V, if D1 and D2 dominate u. Further (D1,D2) is a dominating pair, if (D1,D2) dominates all vertices in V.The total cardinality of a pair (D1,D2) is |D1|+|D2|, and the minimum cardinality of a dominating pair is the disjoint domination number γγ(G) of G. As mentioned earlier, by Ore’s observation, γγ(G)≤|V(G)| for every graph G without isolated vertices and Hedetniemi et al. characterized all extremal graphs for this bound. In this connection, the existence of two disjoint minimum dominating sets in trees was first studied by Bange et al. [10]. In a related paper, Haynes and Henning [11] studied the existence of two disjoint minimum independent dominating sets in a tree.Another application of finding two disjointγ sets is the one in respect of networks. In any network (or graphs), dominating sets are central sets, and they play a vital role in routing problems in parallel computing [12]. Also finding efficient dominating sets is always concern in finding optimal central sets in networks [13]. Suppose that S is a γ-set in a graph (or network) G, when the network fails in some nodes in S, the inverse dominating set in V-S will take care of the role of S. In this aspect, it is worthwhile to concentrate on dominating and inverse dominating sets. Note that γ'(G)≥γ(G). From the point of networks, one may demand γ′(G)=γ(G), where as many graphs do not enjoy such a property. For example consider the star graph K1,n. Clearly γ(K1,n)=1 where as γ'(K1,n)=n. If we consider the graph G=K1,n□K2 with n≥3, then γ(G)=2 and γ′(G)=n. In both the cases if n is large, then γ′(G) is sufficiently large compare to γ(G).The purpose of this paper is to characterize all graphsG with δ(G)≥2 for which γ(G)+γ′(G)=n-1. In this regards, it may be possible that γ′(G) is larger than γ(G) and γ(G)+γ′(G)=n-1. But we prove that graphs G with γ(G)+γ′(G)=n-1 having exactly two disjoint minimum dominating sets. Hereafter G denotes a simple graph on n vertices with no isolated vertices. The minimum degree of a graph G is denoted by δ(G). The set of neighbors of a vertex v in a graph G is denoted by NG(v), and the set of neighbors of v in an induced subgraph of G induced by A⊆V(G) is denoted by NA(v). Also Pn and Cn denote the path and cycle on n vertices, respectively. The Cartesian product of graphs G1 and G2 is the graph G1□G2 whose vertex set is V(G1)×V(G2) and whose edge set is the set of all pairs (u1,v1)(u2,v2) such that either u1u2∈E(G1) and v1=v2 or v1v2∈E(G2) and u1=u2.Let us first recall the following characterizations of graphs for whichγ(G)+γ′(G)=n.Theorem 1.1 (see [7, Theorem 2],).
LetG be a connected graph on n vertices with δ(G)≥2. Then γ(G)+γ′(G)=n if and only if G=C4.Theorem 1.2 (see [7, Theorem 3],).
LetG be a connected graph on n vertices with n≥1 and δ(G)=1. Let L⊆V be the set of all degree one vertices and S=N(L). Then γ(G)+γ'(G)=n if and only if the following two conditions hold:(1)
V-S is an independent set and(2)
for every vertexx∈V-(S∪L), every stem in N(x) is adjacent to at least two leaves.


## 2. Graphs withγ(G)+γ′(G)=n-1

Tamizh Chelvam and Grace Prema [8] characterized graphs for which γ(G)=γ'(G)=(n-1)/2. In this context, we attempt to characterize graphs G with δ(G)≥2 for which γ(G)+γ'(G)=n-1. To attain this aim, we first present the theorem which is useful in the further discussion. To prove the following theorem, since no better proof technique is available, authors prefer case by case analysis.Theorem 2.1.
LetG be a connected graph on n vertices with δ(G)≥2. Then γ(G)+γ'(G)=n-1 implies that γ(G)=γ'(G).Proof.
LetD be a γ-set of G and D′ be a γ′-set of G with respect to D. Note that γ(G)≤γ′(G). Assume that γ(G)+γ'(G)=n-1, and let V(G)-{D∪D′}={w}. Let S⊆D be those vertices that are adjacent to more than one vertex in D′. Suppose that γ(G)<γ'(G). Then |D|<|D′| and so S≠∅. Let S′=N(S)∩D′.
Claim  1. There is at most one vertex in S′ which is adjacent to a vertex in D-S.
Suppose not, there are at least two verticest′, r′ in S′ and t,r∈D-S such that t' is adjacent to t and r' is adjacent to r. Then either both t,r∈D-S are adjacent to w or at least one of t,r is not adjacent to w.
Suppose that botht,r∈D-S are adjacent to w. Since t′, r′ are the only vertices in V(G)-{D∪{w}} which are adjacent to t,r, and t',r' are dominated by some vertices in S, D1=D∪{w}-{t,r}⊂D is a dominating set of G, which is a contradiction to the fact that D is a γ-set of G.
When at least one of them, sayt, is not adjacent to w. Since t∈D-S and δ(G)≥2, t is adjacent to a vertex u in D. Therefore D1=D-{t} is a dominating set of G, which is a contradiction to the fact that D is a γ-set of G. Hence, at most one vertex t′∈S′ which is adjacent to a vertex in D-S. By similar argument as given above, one can prove that t′ is adjacent to exactly one vertex in D-S. Let us take
(2.1)S1′={S′-{t'}ift′exists,S′otherwise.
Note that each vertex inS has at least two neighbors in S' and so S1′≠∅.
Claim  2. (S1′ is independent.)
Suppose that there exists a vertexx′∈S1′ which is adjacent to y′∈S1′. Suppose that w is not adjacent to both x′ and y′. By the fact that each vertex in S has at least two neighbors in D′ and Claim 1, D'-{x′} is a γ′-set of G, a contradiction. If w is adjacent to one of x′ or y′, say x′, then D′-{y'} is a γ′-set of G, which is a contradiction. Hence S1′ is independent.
Now we have the following three possibilities.(1)
w is not adjacent to any of the vertices in S1′.(2)
w is adjacent to exactly one vertex in S1′.(3)
w is adjacent to more than one vertex in S1′.
Case  1. Suppose that w is not adjacent to any of the vertices of S1′. If there exists x′∈S1′ which is adjacent to a vertex in D′-S1′, then D′-{x′} is a γ′-set with respect to D, a contradiction. Therefore, Claim 2 along with δ(G)≥2 together implies that each vertex in S1′ has at least two neighbors in S. Suppose that there exists a vertex x∈S which is adjacent to y∈S, then, as in the proof of Claim 2, we get that either D-{x} or D-{y} is a γ-set of G, a contradiction. Thus S is independent.
Case  1.1. Suppose that there exists a pair of vertices u,v∈S such that NS1′(u)∩NS1′(v)={u′} for some u′∈S1′.
Case  1.1.1.   If w is adjacent to a vertex in D-{u,v}, then, by the assumption in Case 1.1, the vertices in S1′-{u′}, dominated by either u or v, are also adjacent to some vertex in S-{u,v}, and so D-{u,v}∪{u′} is a γ-set of G, which is a contradiction.
Case 1.1.2. If w is adjacent to one of u or v, say u, and let u′≠v′∈NS1′(v). Note that by assumption in Case 1, w is not adjacent to u′ as well as v′.
If there existsx∈S such that NS1′(x)={u′,v′}. Suppose that there exists no vertex in S1′-{u',v′} which is adjacent to only v and x, and then D-{v,x}∪{v′} is a γ-set of G, which is a contradiction. If there exists x′∈S1′-{u',v′} such that NS(x′)={v,x}, then D1=D-{v}∪{v′} is a γ-set of G and D1′=D'-{v′,x′}∪{v} is a γ′-set of G with respect to D1, a contradiction. If there exists y∈S-{u,v,x} such that y is adjacent to v′ and x′ only, then by similar argument one can get a contradiction in all the cases.
If there is no vertexx∈S such that NS1′(x)={u',v′}, then, by Claim 2, D1=D-{v}∪{v′} is a γ-set of G, and so D1′=D-{u',v′}∪{v} is a γ′-set of G, which is a contradiction.
Case  1.2. Suppose that, for each pair of vertices x,y∈S, there exist at least two vertices x′,y′∈S1′ such that {x′,y′}⊆NS1′(x)∩NS1′(y).
Case  1.2.1. Suppose that, for some u′,v′∈S1′, there exists at most one vertex u∈S such that NS(u′)∩NS(v′)={u}. If w is adjacent to a vertex in D-{u}, then D1=D-{u}∪{u′} is a γ-set, and so D1′=D′-{u′,v′}∪{u} is a γ′-set of G, a contradiction. If ND(w)={u}, then D1=D-{u}∪{w} is a γ-set and so D1′=D'-{u′,v′}∪{u} is a γ′-set of G, a contradiction.
Case  1.2.2. Suppose that, for each pair of vertices x′,y′∈S1′, there exist at least two vertices x,y∈S such that {x,y}⊆NS(x′)∩NS(y′). Note that |S|≥2 and |S1′|≥2. Assume that |S|=k and S={u1,u2,…,uk}. If w is adjacent to some vertex in S, say u1, then by the assumption in Case 1.2, there exist u2∈S and u1′,u2′∈S1′ such that 〈{u1,u2,u1′,u2′}〉=K2,2 as S, and S1′ are independent.
Assume that|S|=k≥3. Suppose that Ns1′(u3)={u1′,u2′}. Since u2′ dominates both u2,u3 and u1′,u2′ are the vertices dominated by u2 and u3, D1=D-{u3,u2}∪{u2′} is a γ-set of G, a contradiction. Thus u3 is adjacent to vertex in S-{u1′,u2′}, say u3′. Suppose that NS(u3′)⊆{u1,u2,u3}. Since each pair of vertices in S has at least two neighbors, we have D1=D-{u2}∪{u2′} as a γ-set and D1′=D′-{u2′,u3′}∪{u2} as a γ′-set of G, a contradiction. Thus u3′ is adjacent to some vertex in S-{u1,u2,u3}, take u4. Proceed like this up to uk, and let uk′∈Ns1′(uk). If NS(uk′)⊆S, then D1=D-{uk-1}∪{uk-1′} is a γ-set, and so D1′=D′-{uk-1′,uk′}∪{uk-1} is a γ′-set of G, a contradiction. Hence uk′ is adjacent to at least one vertex in S-{u1,…,uk}=∅, which is not possible.
Let|S|=k=2. If |S1′|≥3, then u3′ is adjacent to u1 and u2 only. Therefore D1=D-{u2}∪{u2′} is a γ-set, and D1′=D′-{u2′,u3′}∪{u2} is a γ'-set of G, a contradiction. If |S1′|=2, then D=D′, which is a contradiction.
Case  2. Suppose that w is adjacent to exactly one vertex x′∈S1′. If u′∈S1′-{x′} is adjacent to a vertex in D′, then D′-{u′} is a γ′-set of G, a contradiction. Thus every vertex in S1′-{x'} has at least two neighbors in S.
If|S1′|≥3, then, as in Case 1, replacing S1′ by S1′-{x′}, we get contradiction in all the possibilities.
Let|S1′|=2 and S1′={x′,y′}. Since y′ has at least two neighbors in S, |S|≥2 and so |S|≥|S1′|, which is contradiction to |D|<|D′|.
If|S1′|=1, then since |D|<|D'|, S=∅, a contradiction to S≠∅.
Case  3. Suppose w is adjacent to more than one vertex in S1′, say u′,v′∈S1′. If no vertex in S is adjacent to only u′,v′, then D'-{u',v′}∪{w} is a γ-set of G, a contradiction. Thus there exists a vertex u∈S such that NS1′(u)={u′,v′}. If w is adjacent to u, then D1=D-{u}∪{w} is a γ-set and D1′=D'-{u′,v′}∪{u} is a γ'-set of G, a contradiction. Now let u≠x∈ND(w) and let x'∈ND′(x).
Suppose that there existsy∈D-{x} such that y∈N(x′). Suppose there exists z∈D-{u,x} such that ND'(z)⊆{u′,v′,x′}. Then D-{u,z}∪{u′} is a γ-set of G, a contradiction. Otherwise, D1=D-{u,x}∪{u′,w} is a γ-set and D1′=D′-{u′,v′,x′}∪{x,u} is a γ′-set of G, a contradiction.
Suppose thatND(x′)={x}. If x′ is adjacent to w, then, D′-{u′,x′}∪{w} is a γ′-set of G. If x′ is not adjacent to w, then as δ(G)≥2, x′ is adjacent to at least a vertex say y′∈D′. Since x′∈N(y′), x,u′∈N(w) and ND(x′)={x}, we get D′-{u′,x′}∪{w} is a γ′-set of G, which is a contradiction.
Hence,γ(G)=γ′(G).Bange et al. [10] characterized trees with two disjoint minimum dominating sets. In the following corollary, we give the necessary condition for graphs with minimum degree at least two having two disjoint minimum dominating sets.Corollary 2.2.
LetG be a connected graph on n vertices with δ(G)≥2. If γ(G)+γ′(G)=n-1, then G has two disjoint γ-sets.The following example shows that in general Theorem2.1 is not true whenever δ(G)=1.Example 2.3.
(
i
) Consider the graph P6, the path on 6 vertices. Then γ(P6)=2 and γ′(P6)=3. Therefore, γ(P6)+γ′(P6)=5 but γ(P6)≠γ′(P6).
(
ii
) Consider the graph G in Figure 1. Clearly, γ(G)=3 and γ′(G)=4. Therefore γ(G)+γ′(G)=7=n-1 whereas γ(G)≠γ′(G).Figure 1
GraphG.Lemma 2.4.
LetG be a connected graph with δ(G)≥2. Then γ(G)+γ′(G)=n-1 if and only if γ(G)=γ′(G)=⌊n/2⌋, and n is odd.Proof.
Ifγ(G)+γ′(G)=n-1, then, by Theorem 2.1, γ(G)=γ'(G). Therefore γ(G)=γ′(G)=(n-1)/2, and hence n is odd. Conversely, assume that γ(G)=γ′(G)=⌊n/2⌋ and n is odd. Since n is an odd integer, we get γ(G)+γ′(G)=n-1.Let𝒞 and 𝒟 be the families of graphs given in Figures 2 and 3, respectively.Figure 2
Graphs in family𝒞.Figure 3
Graphs in family𝒟.Note that the class𝒞 is a subclass of the class 𝒜, and the class 𝒟 is same as the class ℬ where 𝒜 and ℬ are classes given in Theorem 2.6 [1, Page -45].The next theorem characterizes all connected graphsG with δ(G)≥2 for which γ(G)+γ′(G)=n-1. By Lemma 2.4 and Lemma 2.4 [1], we get the main theorem of this paper.Theorem 2.5.
LetG be a connected graph with δ(G)≥2. Then γ(G)+γ′(G)=n-1 if and only if G∈𝒞∪𝒟.It may be worth noting that, for any graphG, the disjoint domination number γγ(G)≤γ(G)+γ′(G). Due to this, we get an upper bound for γγ(G) and γ(G)+γ′(G) which is better than the Ore’s observation for disjoint domination number and sum of domination number and inverse domination number [7].Corollary 2.6.
LetG be a connected graph with δ(G)≥2 and G∉{H1,…,H11}. Then γγ(G)≤γ(G)+γ′(G)≤n-2.We suggest the following problems for further study in this direction.Open Problems
(1) Find a necessary and sufficient condition for a graphG with δ(G)=1 and γ(G)+γ′(G)=n-1.
(2) Characterize all connected graphsG with δ(G)≥2 for which γ(G)+γ′(G)=n-2.



---

*Source: 831489-2012-08-27.xml*