# Some New Perspectives on Global Domination in Graphs

Authors: S. K. Vaidya; R. M. Pandit
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

A dominating set is called a global dominating set if it is a dominating set of a graphG and its complement G¯. Here we explore the
possibility to relate the domination number of graph G and the global
domination number of the larger graph obtained from G by means of
various graph operations. In this paper we consider the following problem: Does the global domination number remain invariant under any graph operations? We present an affirmative answer to this problem and establish several results.


---

## Body

## 1. Introduction

The domination in graphs is one of the concepts in graph theory which has attracted many researchers to work on it. Many variants of dominating sets are available in the existing literature. This paper is focused on global domination in graphs.We begin with simple, finite, and undirected graphG=(V,E) with |V|=n. The set S⊆V is called a dominating set if N[S]=V. A dominating set S is called a minimal dominating set (MDS) if no proper subset S′ of S is a dominating set.The minimum cardinality of a dominating set inG is called the domination number of G denoted by γ(G), and the corresponding dominating set is called a γ-set of G.The complementG¯ of G is the graph with vertex set V in which two vertices are adjacent in G¯ if and only if they are not neighbors in G.A dominating setS of G is called a global dominating set if it is also a dominating set of G¯. The global domination number γg(G) is the minimum cardinality of a global dominating set of G. The concept of global domination in a graph was introduced by Sampathkumar [1]. This concept is remained in focus of many researchers. For example, the global domination number of boolean function graph is discussed by Janakiraman et al. [2]. The NP completeness of global domination problems is discussed by Carrington [3] and by Carrington and Brigham [4]. The global domination number for the larger graphs obtained from the given graph is discussed by Vaidya and Pandit [5] while Kulli and Janakiram [6] have introduced the concept of total global dominating sets. The discussion on global domination in graphs of small diameters is carried out by Gangadharappa and Desai [7].The wheelWn is defined to be the join Cn-1+K1 where n≥4. The vertex corresponding to K1 is known as apex vertex, and the vertices corresponding to cycle Cn-1 are known as rim vertices.Duplication of an edgee=uv of a graph G produces a new graph G1 by adding an edge e′=u′v′ such that N(u)=N(u′) and N(v)=N(v′).The shadow graphD2(G) of a connected graph G is constructed by taking two copies of G, say G′ and G′′. Join each vertex u′ in G′ to the neighbors of the corresponding vertex u′′ in G′′.A vertex switchingGv of a graph G is the graph obtained by taking a vertex v of G, removing all the edges incident to v and adding edges joining v to every vertex not adjacent to v in G.For the various graph theoretic notations and terminology we follow West [8] while the terms related to the concept of domination are used in the sense of Haynes et al. [9].Here we consider the problem: Does the global domination number remain invariant under any graph operations? We present here an affirmative answer to this question for the graphs obtained by various graph operations onCn and Wn. Moreover, we obtain the domination number and the global domination number for the shadow graph of Pn and the graphs obtained by switching of a vertex in Cn as well as in Wn.


## 2. Main Results

Theorem 1.
IfCn′ is a graph obtained by duplication of an edge in Cn(n≠3,n≠5) by an edge then every γ-set of Cn′ is a global dominating set of Cn′ and γ(Cn′)=γg(Cn′)=⌈n/3⌉. Furthermore, the global domination number remains invariant under the operation of duplication of an edge for Cn.Proof.
LetCn′ be a graph obtained by duplication of an edge in Cn(n≠3,n≠5). Without loss of generality, let the edge e=v1v2 of Cn be duplicated by an edge e′=v1′v2′.
LetS be a γ-set of Cn′. Then S is a dominating set of Cn′. Now, any two distinct vertices vi and vj with d(vi,vj)≠2 in Cn′ are enough to dominate Cn′¯ because the vertices which are not in N[vi] must belong to N[vj] in Cn′¯. Since every γ-set of Cn′ contains at least two such vertices vi and vj, it is a dominating set of Cn′¯. Hence, every γ-set of Cn′ is a dominating set of Cn′ as well as of Cn′¯. Consequently, every γ-set of Cn′ is a global dominating set of Cn′.
Now, consider aγ-set of Cn′:
(1)S={{v3,v6,v9,…,v3j}ifn≡0(mod3),{v3,v6,v9,…,v3j}∪{vn}ifn≡1or2(mod3)for1≤j≤⌊n3⌋.
Sinced(v3)=3=d(vn)=Δ(Cn′), S must contain v3 and vn for minimum cardinality. Also, to retain the minimum cardinality of S, it must contain the vertices v3j(2≤j≤⌊n/3⌋). That is, |S|≥⌈n/3⌉. Now, S being a γ-set of Cn′ is a global dominating set of Cn′ with minimum cardinality ⌈n/3⌉. This implies that γ(Cn′)=γg(Cn′)=⌈n/3⌉. Also, as reported in Sampathkumar [1], γg(Cn)=⌈n/3⌉(n≠3,n≠5). Hence, γg(Cn)=γg(Cn′)=⌈n/3⌉(n≠3,n≠5). Thus, the global domination number remains invariant under the operation of duplication of an edge by an edge in Cn.Theorem 2.
IfG is the graph obtained by duplicating each edge of Cn by an edge then every γ-set of G is a global dominating set of G and γ(G)=γg(G)=n.Proof.
LetS be a γ-set of G. Then S is a dominating set of G. Now, any two adjacent vertices vi and vj in G are enough to dominate G¯ because the vertices which are not in N[vi] in G¯ must belong to N[vj] in G¯. Since every γ-set of G contains at least two such vertices vi and vj, every γ-set of G is a dominating set of G¯. Hence, every γ-set of G is a dominating set of G as well as of G¯. This implies that every γ-set of G is a global dominating set of G.
Letv1,v2,…,vn be the vertices of Cn. Consider a γ-set of G, S={v1,v2,…,vn}. S being a γ-set of G is a dominating set of G with minimum cardinality. Moreover, since v1,v2,…,vn are the vertices of maximum degree in G and from the nature of the graph G, it is clear that S={v1,v2,…,vn} is of minimum cardinality. Hence, S is a γ-set of G with minimum cardinality n. Therefore, γ(G)=n. Now, S being a γ-set of G is a global dominating set of G with minimum cardinality n which implies that γ(G)=γg(G)=n as required.The following Theorem3 can be proved by the arguments analogous to the above Theorem 2.Theorem 3.
IfG is the graph obtained by duplicating each edge of Pn by an edge then every γ-set of G is a global dominating set of G and γ(G)=γg(G)=n.Theorem 4.
IfWn′ is a graph obtained by duplicating an edge of Wn by an edge then
(2)γg(Wn)=γg(Wn′)={4ifn=43otherwise.
That is, the global domination number remains invariant under the operation of duplication of an edge inWn.Proof.
LetV(Wn)={v1,v2,…,vn-1}∪{c}, where c is the apex vertex of Wn.
It is easy to observe that(3)γg(Wn)={4ifn=43otherwise.
Case I (When a rim edge of Wn is duplicated by an edge). Without loss of generality, let the rim edge e=v1v2 of Wn be duplicated by an edge e′=v1′v2′.
Forn=4, since the vertex c is adjacent to each vertex of Wn′, it must belong to any global dominating set of Wn′. Moreover, any two vertices are adjacent to third vertex other than c in Wn′. Therefore, any global dominating set of Wn′ must contain at least four vertices including c which implies that γg(Wn′)=4.
Forn>4, the vertex c dominates Wn′ while the vertex c and any two adjacent rim vertices of Wn are enough to dominate Wn′¯. Therefore, any global dominating set of Wn′ must contain at least three vertices of Wn′. This shows that γg(Wn′)=3.
Thus,(4)γg(Wn′)={4ifn=43otherwise.
Case II (When a spoke edge of Wn is duplicated by an edge). Without loss of generality, let the spoke edge e=cv1 be duplicated by an edge e′=c′v1′.
Forn=4, any two vertices in Wn′ are adjacent to the third vertex and also any three vertices are adjacent to the fourth vertex in Wn′. Therefore, any global dominating set of Wn′ must contain at least four vertices which implies that γg(Wn′)=4.
Forn>4, clearly any global dominating set of Wn′ must contain either c or c′ to achieve its minimum cardinality. Moreover, any two adjacent rim vertices of Wn and the vertex c are enough to dominate Wn′¯ and they also dominate Wn′. This implies that γg(Wn′)=3.
Thus,(5)γg(Wn′)={4ifn=43otherwise.
Hence, we have proved that(6)γg(Wn)=γg(Wn′)={4ifn=43otherwise.
That is, the global domination number remains invariant under the operation of duplication of an edge inWn.Theorem 5.
Everyγ-set of D2(Pn) is a global dominating set of D2(Pn), and
(7)γ(D2(Pn))=γg(D2(Pn))={n2ifn≡0(mod4)⌊n2⌋+1otherwise.Proof.
Consider two copies ofPn. Let v1,v2,…,vn be the vertices of the first copy of Pn and u1,u2,…,un the vertices of the second copy of Pn.
IfS is a γ-set of D2(Pn) then S is a dominating set of D2(Pn). Now, any two adjacent vertices vi and vj of D2(Pn) are enough to dominate D2(Pn)¯ because the vertices which are not in N[vi] in D2(Pn)¯ must belong to N[vj] in D2(Pn)¯. Since every γ-set of G contains at least two such vertices vi and vj, every γ-set of D2(Pn) is a dominating set of D2(Pn)¯. Hence, every γ-set of D2(Pn) is a dominating set of D2(Pn) as well as of D2(Pn)¯. This implies that every γ-set of D2(Pn) is a global dominating set of D2(Pn).
Case I
(
n
=
2
,
3
). For D2(P2) and D2(P3), clearly S={v1,v2} and S={v2,v3} are γ-sets as well as global dominating sets with minimum cardinality respectively. Therefore, γ(D2(Pn))=γg(D2(Pn))=2=⌊n/2⌋+1 for n=2,3.
Case II
(
n
≥
4
). (i) For n≡0(mod4)(i.e., n=4k,k∈N), consider a γ-set S={v2+4i,v3+4i/0≤i≤k-1} where |S|=n/2.
(ii) Forn≡1(mod4)(i.e., n=4k+1,k∈N), consider a γ-set S={v2+4i,v3+4i/0≤i≤k-1}∪{vn-1} where |S|=⌊n/2⌋+1.
(iii) Forn≡2or3(mod4)(i.e., n=4k+2 or n=4k+3,k∈N), consider a γ-set S={v2+4i,v3+4i/0≤i≤k-1}∪{vn-2,vn-1} where |S|=⌊n/2⌋+1.
Now,S being a γ-set of D2(Pn) is a global dominating set of D2(Pn) with minimum cardinality implying that |S|=γ(D2(Pn))=γg(D2(Pn)).
Thus, we have proved that(8)γ(D2(Pn))=γg(D2(Pn))={n2ifn≡0(mod4)⌊n2⌋+1otherwise.Theorem 6.
IfGv is a graph obtained by switching of a vertex in cycle Cn(n≥8) then γ(Gv)=γg(Gv)=3.Proof.
Letv1,v2,…,vn be the successive vertices of G=Cn and Gv denotes the graph obtained by switching of a vertex v of G. Without loss of generality, let the switched vertex be v1.
Consider a setS={v1,v2,vn}. Then S is a dominating set of Gv as all the vertices except the pendant vertices, namely, v2 and vn, are in N[v1] while v2 and vn are already in S. Moreover, the set S is a minimal dominating set of Gv because for any vi∈S, the set S-{vi} does not dominate the vertex vi of Gv. Furthermore, the vertex v1 dominates (n-2) vertices of Gv and the remaining two vertices are pendant vertices. Therefore, at least three vertices are required to dominate Gv, and hence |S|≥3. Thus, S being a minimal dominating set with minimum cardinality is a γ-set of Gv which implies that γ(Gv)=3.
Now, we claim that the pendant vertices inGv are enough to dominate remaining vertices of Gv¯. Since the vertex which is not in N[v2] in Gv¯ must belong to N[vn] in Gv¯, any S⊆V containing v2 and vn will be a dominating set of Gv¯. Thus, S is a dominating set of Gv as well as of Gv¯. This implies that S is a global dominating set of Gv.
SinceS is a γ-set of Gv as above, it is of minimum cardinality. Therefore, γg(Gv)=3. Thus, γ(Gv)=γg(Gv)=3 as required.Theorem 7.
IfGv is a graph obtained by switching of a rim vertex in a wheel Wn then
(9)γg(Gv)={2ifn=4,53otherwise.Proof.
Letv1,v2,…,vn-1 be the successive rim vertices of G=Wn and Gv denotes the graph obtained by switching of the vertex v of G. Without loss of generality, let the switched vertex be v1. Let c be the apex vertex of Wn.
Case I
(
n
=
4,5
). It is easy to observe that S={v1,v3} is a global dominating set of Gv with minimum cardinality. Therefore, γg(Gv)=2 for n=4,5.
Case II
(
n
≥
6
). Consider a set S={c,v3,v4}. Then, S is a dominating set of Gv as all the vertices except the vertex v1 are in N[c] in Gv while v1 is dominated by v3. Now, the vertex v3 dominates all the vertices of Gv¯ except the vertices v1,v2,v4, and c. But the vertices v1 and v2 are dominated by the vertices c and v4 in Gv¯ respectively while the vertices v4 and c are already in S. Therefore, S is a dominating set of Gv¯. Hence, S is a dominating set of Gv as well as of Gv¯. That is, S is a global dominating set of Gv. Moreover, two vertices, namely, c and either of the vertices from v3 and v4 are enough to dominate Gv. Since any two vertices in Gv are adjacent to the third vertex in Gv, at least three vertices are essential to dominate Gv¯. This implies that γg(Gv)=3. Thus, we have proved that
(10)γg(Gv)={2ifn=4,53otherwise.Theorem 8.
IfGv is the graph obtained by switching of the apex vertex in wheel Wn then γ(Gv)=γg(Gv)=⌈(n-1)/3⌉+1.Proof.
Letv1,v2,…,vn-1 be the successive rim vertices of G=Wn and let Gv denote the graph obtained by switching of the vertex v of G. Let the switched vertex be the apex vertex c of Wn.
Becausec is adjacent to every other vertex in G, c is not adjacent to any other vertex in Gv. Therefore, any dominating set for Gv must contain c. This implies that any global dominating set of Gv must contain c.
Case I
(
n
=
4,6
). It is easy to observe that S={c,v1} and S={c,v1,v3} are γ-sets as well as global dominating sets of Gv of W4 and W6 respectively with minimum cardinality.
Therefore,(11)γ(Gv)=γg(Gv)={2=⌈(4-1)3⌉+1forn=4,3=⌈(6-1)3⌉+1forn=6.
Thus,γ(Gv)=γg(Gv)=⌈(n-1)/3⌉+1 for n=4,6.
Case II
(
n
≠
4,6
). The vertex c will be the isolated vertex in Gv. Hence, Gv=Cn-1∪K1. Therefore, γ(Gv)=γ(Cn-1)+1. But as reported in Sampathkumar [1], γ(Cn-1)=⌈(n-1)/3⌉. This implies that γ(Gv)=⌈(n-1)/3⌉+1.
Because every dominating set ofGv must contain c and c is enough to dominate Gv¯, γ(Gv)=γg(Gv).
Hence,γ(Gv)=γg(Gv)=⌈(n-1)/3⌉+1 for n≠4,6.
Thus, we have proved thatγ(Gv)=γg(Gv)=⌈(n-1)/3⌉+1 as required.


## 3. Concluding Remarks

The concept of global domination is remarkable as it relates the dominating sets of a graph and its complement. We have explored this concept in the context of some graph operations and also have investigated the domination number and the global domination number for the larger graph obtained by some graph operations on a given graph. The invariance parameter for global domination is also explored.



---

*Source: 201654-2013-08-20.xml*