# Some New Results on Global Dominating Sets

Authors: S. K. Vaidya; R. M. Pandit
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

A dominating set is called a global dominating set if it is a dominating set of a graphG and its complement G¯. A natural question arises: are there any graphs for which it is possible to relate the domination number and the global domination number? We have found an affirmative answer to this question and obtained some graphs having such characteristic.


---

## Body

## 1. Introduction

We begin with finite and undirected simple graphG=(V,E) of order n. The set S⊆V of vertices in a graph G is called a dominating set if every vertex v∈V is either an element of S or is adjacent to an element of S. A dominating set S is a minimal dominating set (MDS) if no proper subset S′⊂S is a dominating set.The minimum cardinality of a dominating set ofG is called the domination number of G which is denoted by γ(G) and the corresponding dominating set is called a γ-set of G.The open neighborhoodN(v) of v∈V is the set of vertices adjacent to v and the closed neighborhood of v is the set N[v]=N(v)∪{v}.The complementG¯ of G is the graph with vertex set V and two vertices are adjacent in G¯ if and only if they are not adjacent in G.A subsetD⊆V is called a global dominating set in G if D is a dominating set of both G and G¯. The global domination number γg(G) is the minimum cardinality of a global dominating set in G. The concept of global domination in graph was introduced by Sampathkumar [1].The upper bounds of global domination number are investigated by Brigham and Dutton [2] as well as by Poghosyan and Zverovich [3], while the global domination number of Boolean function graph is studied by Janakiraman et al. [4]. The global domination decision problems are NP-complete as discussed by Carrington [5] and by Carrington and Brigham [6]. The edge addition stable property in the context of global domination and connected global domination for cycle Cn and path Pn is discussed by Kavitha and David [7]. The concept of total global dominating set was introduced by Kulli and Janakiram [8] and they have also characterized total global dominating sets.The wheelWn is defined to be the join Cn-1+K1. The vertex corresponding to K1 is known as apex vertex and the vertices corresponding to cycle are known as rim vertices.A shell graphSn(n>3) is the graph obtained by taking (n-3) concurrent chords in a cycle Cn. The vertex at which all the chords are concurrent is called the apex. The shell graph Sn is also called fan fn-1 that is, Sn=fn-1=Pn-1+K1.Definition 1.1.
The one-point union ofr cycles of length n denoted by Cn(r) is the graph obtained by identifying one vertex of each cycle.
The one-point union ofr cycles C3 is known as friendship graph which is denoted by Fn.Definition 1.2 (see Shee and Ho [9]).
LetG=(V,E) be a graph and let G1,G2,G3,…,Gr, r>2 be r copies of a graph G. Then, the graph obtained by adding an edge from Gi to Gi+1 for i=1,2,…,r-1 is called path union of G.Definition 1.3.
Consider two copies of a graphG, namely, G(1) and G(2). Then, G1=〈G(1):G(2)〉 is the graph obtained by joining the vertices of degree (n-1) of each graph to a new vertex x.Definition 1.4.
Considerr-copies of a graph G, namely, G(1),G(2),G(3),⋯,G(r). Then, G1=〈G(1):G(2):G(3):⋯:G(r)〉 is the graph obtained by joining the vertices of degree (n-1) of each G(p-1) and G(p) to a new vertex xp-1, where 2≤p≤k.Definition 1.5.
Consider two copies of a graphG, namely, G(1) and G(2). Then, G1=〈G(1)▲G(2)〉 is the graph obtained by joining the vertices of degree (n-1) of each graph by an edge as well as to a new vertex x.Definition 1.6.
Considerr-copies of a graph G, namely, G(1),G(2),G(3),⋯,G(r). Then, G1=〈G(1)▲G(2)▲G(3)▲…▲G(r)〉 is the graph obtained by joining the vertices of degree (n-1) of each G(p-1) and G(p) by an edge as well as to a new vertex xp-1, where 2≤p≤k.
For the various graph theoretic notations and terminology we follow West [10], while the terms related with the concept of domination are used in the sense of Haynes et al. [11].
In the present paper we investigate some results on global dominating sets in the context of one-point union of cycles and path union of some graph families.


## 2. Main Results

Theorem 2.1.
IfG is a one-point union of finite number of copies of cycle C3, then γg(G)=γ(G)+2.Proof.
Considerr-copies of cycle C3 in G and let c be the vertex in common for these r-copies. Because c is adjacent to every other vertex in G, c is not adjacent to any other vertex in the complement of G. Therefore, any dominating set for the complement of G must contain c. Hence, any global dominating set of G must contain c.
Letv1 and v2 be the vertices of a cycle C3 other than c in G. Now, since vertices both c and v1 are adjacent to third vertex v2 of a cycle C3 in G, at least three vertices are essential to dominate G,¯ which also dominate G. Therefore, γg(G)=3. Moreover, S={c} is the only γ-set of G as c is the only vertex of degree (n-1) in G. Hence, γ(G)=1.
Thus,γg(G)=γ(G)+2 as required.Theorem 2.2.
IfG is a one-point union of finite number of copies of cycle Cn, then γ(G)=γg(G)=(⌈n/3⌉-1)r+1 for n>3.Proof.
Considerr-copies of cycle Cn in G and let c be the vertex in common for these r-copies. Since c is the vertex with maximum degree, it must belong to any global dominating set corresponding to G for minimum cardinality.
Now, it is easy to observe thatγg(Cn)=⌈n/3⌉ for n≠3, n≠5. Therefore, any global dominating set corresponding to G must contain (⌈n/3⌉-1) vertices from each copy of Cn(n≠3,n≠5) other than the vertex c for the minimum cardinality. Thus, γg(G)=(⌈n/3⌉-1)r+1 for n≠3,n≠5.
Forn=5, we argue that any two nonadjacent vertices of C5 dominate C5. If G is a one-point union of r- copies of C5, then the vertex c, being a common vertex of G, and a vertex v nonadjacent to c from each r-copy of C5 is the minimum vertices which dominate G. These vertices also dominate G¯ because a vertex v nonadjacent to c from any two copies of C5 are enough to dominate G¯. Therefore, γg(G)=r+1=(1)r+1=(⌈5/3⌉-1)r+1.
Thus,γg(G)=(⌈n/3⌉-1)r+1 for n>3.
The set, being a global dominating set with minimum cardinality, is an MDS with minimum cardinality. that is, the set is also aγ-set of G. Thus, γ(G)=γg(G)=(⌈n/3⌉-1)r+1 for n>3 as required.Theorem 2.3.
LetG be a path union of finite number of copies of the graph of order n having at least one vertex of degree (n-1). Then, S is a γ-set of G if and only if S is a global dominating set of G. Also, γg(G)=γ(G).Proof.
Letv1,v2,v3,…,vr be the vertices of degree (n-1) from each G1,G2,G3,…,Gr, respectively.
Suppose thatS is a γ-set of G. Now from the adjacency of the vertices in G, it is easy to observe that S={v1,v2,v3,…,vr} is the only γ-set of G except for the path union of W4.
In case ofW4, a set comprises of one vertex of degree (n-1) from each G1,G2,G3,…,Gr or a vertex from each G1,G2,G3,…,Gr will be a γ-set. Because each vertex vi(i=1,2,…,r) of Gi dominates all the vertices of G¯ except its adjacent vertices and these adjacent vertices are dominated by vi-1 or vi+1, consequently any two adjacent vertices vi are enough to dominate all the vertices of G¯. Hence, S is a dominating set of G¯.
Now,S being a γ-set of G, it is also a dominating set of G. Thus, S is a dominating set of both G and G¯, which implies that S is a global dominating set of G.
Conversely, suppose thatS is a global dominating set of G, that is, S is a dominating set of both G and G¯.
ConsiderS={v1,v2,v3,…,vr}. On removing any of the vertex vi(i=1,2,…,r) from S, the set S-{vi} will not dominate N[vi]. Therefore, S-{vi} is not a dominating set of G. This implies that S is an MDS of G. Each vi being a vertex of degree (n-1), clearly S is of minimum cardinality. Hence, S is a γ-set of G.
Thus, we have proved thatS is a γ-set of G if and only if it is a global dominating set of G.
SinceS being a γ-set of G, it is an MDS with minimum cardinality which implies that γg(G)=γ(G) as required.Theorem 2.4.
LetG1=〈G(1):G(2)〉. Then,(i)
γg(G1)=γ(G1) where G can be W4, Kn and(ii)
γg(G1)=γ(G1)+1 where G can be Wn(n>4), Sn, Fn, K1,n.Proof.
LetG(1) and G(2) denote the two copies of the graph G. Let v1 and v2 be the vertices of degree (n-1) in G(1) and G(2) respectively. Suppose that x is the vertex adjacent to both v1 and v2.
ConsiderG1=〈G(1):G(2)〉.
(
i
) Let G be either W4 or Kn. Then in order to dominate vertex x in G1, either v1 or v2 is required. If v1∈S, then v1 and any other vertex v from G(2) will dominate G1. Clearly, S={v1,v} is a γ-set of G1. Hence, γ(G1)=2.
Forv≠v2, S is also a dominating set of G1¯ which implies that S is a global dominating set of G1 and is of minimum cardinality. Consequently, γg(G1)=2. Thus, γg(G1)=γ(G1) as required.
(
i
i
) Let G be Wn(n>4), Sn, Fn, or K1,n. Since v1 and v2 are the vertices of degree (n-1) and they are adjacent to the vertex x, S={v1,v2} is the γ-set of G1 which implies that γ(G1)=2.
S
=
{
v
1
,
v
2
} being a γ-set and x is adjacent to both v1 and v2, Sg={v1,v2,x} is a global dominating set of G1 which is of minimum cardinality. This implies that γg(G1)=3.
Hence,γg(G1)=γ(G1)+1 as required.Theorem 2.5.
IfG1=〈G(1):G(2):⋯:G(r)〉 with r>2 where G can be Wn, Sn, Fn, K1,n, or Kn, then γg(G1)=γ(G1).Proof.
LetG(j)(j=1,2,…,r) denote r-copies of graph G and let vj be the vertex of degree (n-1) in G. Suppose that x1,x2,x3,…,xr-1 are the vertices such that vp-1 and vp are adjacent to xp-1 where 2≤p≤r.
ConsiderG1=〈G(1):G(2):⋯:G(r)〉. Construct a dominating set S as follows,
Select a set of verticesvj(j=1,2,…,r) of degree (n-1) from each G(1),G(2),…,G(r), respectively where vj dominates N[vj]. Then, S={v1,v2,v3,…,vr} is a dominating set of G1.
If we remove any ofvj from S, then S-{vj} will not dominate N[vj] which implies that S-{vj} is not a dominating set of G1. Consequently, S is a minimal dominating set. Each vj being a vertex of degree (n-1), clearly S is an MDS with minimum cardinality r. Therefore, γ(G1)=r.
We claim thatS is also a dominating set of G1¯ because any two vertices vi and vj with d(vi,vj)>2 are enough to dominate G1¯. Hence, S is a dominating set of both G1 and G1¯, which implies that γg(G1)=r.
Thus,γg(G1)=γ(G1) as required.The following Theorem2.6 can be proved by the arguments analogous to the above Theorem 2.5.Theorem 2.6.
IfG1=〈G(1)▲G(2)▲⋯▲G(r)〉 with r>2 where G can be Wn, Sn, Fn, K1,n, or Kn, then γg(G1)=γ(G1).On considering the two copies in Theorem2.6, we have the following result.Theorem 2.7.
IfG1=〈G(1)▲G(2)〉 where G can be Wn, Sn, Fn, K1,n, or Kn, then γg(G1)=γ(G1)+1.Proof.
LetG(1) and G(2) denote the two copies of the graph G. Let v1 and v2 be the vertices of degree (n-1) in G(1) and G(2), respectively and let x be the vertex adjacent to v1 and v2 both.
Consider the graphG1=〈G(1)▲G(2)〉. Then as v1 and v2 both being the vertices of degree (n-1) in G(1) and G(2) respectively, the set S={v1,v2} is an MDS with minimum cardinality, that is, S is a γ-set of G1 which implies that γ(G1)=2.
Now,S is not a dominating set of G1¯ because the vertex x is adjacent to both v1 and v2. But S={v1,v2,x} is a dominating set of G1¯ which is also a dominating set of G1, that is, S is a global dominating set of G1. To dominate the vertex x in G1, either v1 or v2 is required in S which is also in a global dominating set of G1. To dominate G1¯, if v1∈S, then a vertex will be adjacent to both v1 and any vertex from G(2). Therefore, at least three vertices are required to dominate G1¯. Consequently, S={v1,v2,x} is a global dominating set of G1 with minimum cardinality, that is, γg(G1)=3.
Hence,γg(G1)=γ(G1)+1 as required.


## 3. Concluding Remarks

We have investigated some results corresponding to the concept of global domination. We have taken up the issue to obtain the global domination number for the larger graph obtained from the given graph. We have established the relations between the domination number and the global domination number for the graphs obtained by some graph operations, namely, one-point union and path union of graphs. More exploration is possible in the context of different graph families.



---

*Source: 852129-2012-11-05.xml*