See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/328240551

Isolate and independent domination number of some classes of graphs

Article  in  AKCE International Journal of Graphs and Combinatorics · October 2018

DOI: 10.1016/j.akcej.2018.08.005

CITATIONS READS

0 165

2 authors:

Shilpa Tushar Bhangale Madhukar M, Pawar

Ramrao Adik Institute of Technology 11 PUBLICATIONS   37 CITATIONS   
1 PUBLICATION   0 CITATIONS   
SEE PROFILE
SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Colouring of posets View project

energy of poset View project

All content following this page was uploaded by Madhukar M, Pawar on 15 October 2018.

The user has requested enhancement of the downloaded file.

Available online at www.sciencedirect.com
ScienceDirect
AKCE International Journal of Graphs and Combinatorics ( ) –
www.elsevier.com/locate/akcej

Isolate and independent domination number of some classes of

graphs
Shilpa T. Bhangale a , Madhukar M. Pawar b , c , ∗
a Engineering Science Department, Ramrao Adik Institute of Technology, Nerul, Navi Mumbai (M.S.) 400-706, India
b P.G. Department of Mathematics, SSVPS’s L. K. Dr. P. R. Ghogrey Science College, Deopur, Dhule (M.S.) 424-005, India
c M.G. Tele Commerce, C. & B. R. Tele Science and K. Tele Management College, Thalner, Tal. Shirpur, Dist. Dhule (M.S.), 425-421, India

Received 2 August 2017; received in revised form 5 July 2018; accepted 19 August 2018
Available online xxxx

Abstract

In this paper we compute isolate domination number and independent domination number of some well known classes of
graphs. Also a counter example is provided, which disprove the result on independent domination for Euler Totient Cayley graph
proved by Uma Maheswari and B. Maheswari and improved it for some sub cases.
⃝c 2018 Kalasalingam University. Publishing Services by Elsevier B.V. This is an open access article under the CC BY-NC-ND
license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Keywords: Domination number; Isolate domination number; Independent domination number; Euler totient

1. Introduction and preliminaries

O. Ore properly introduced domination number in 1962, but before that C. Berge introduced this concept in 1958
under a different name. The motivation for this concept was the classical problem of covering chess board with
minimum number of chess pieces. In recent years much attention has been paid towards the domination theory. It has
been an extensively flourishing research branch in Graph Theory.
Dominating set is a subset S of the vertex set V in graph G = (V, E) such that every vertex v ∈ V (G) − S is
adjacent to at least one vertex in S. If S is a dominating set such that no proper subset of S is a dominating set, then it
is called minimal dominating set and the minimum (maximum) cardinality of a minimal dominating set is known as
the domination number (upper domination number), denoted by γ (G)(Γ (G)). A dominating set which is independent
is called independent dominating set and the minimum (maximum) cardinality of an independent dominating set is
called the independent domination number (upper independent domination number) and it is denoted by γi (G) or
i(G). Upper independent domination number is denoted by β0 (G).
Peer review under responsibility of Kalasalingam University.
∗ Corresponding author at: P.G. Department of Mathematics, SSVPSs L. K. Dr. P. R. Ghogrey Science College, Deopur, Dhule (M.S.) 424-005,
India.
E-mail addresses: [email protected] (S.T. Bhangale), [email protected] (M.M. Pawar).

https://doi.org/10.1016/j.akcej.2018.08.005
0972-8600/⃝ c 2018 Kalasalingam University. Publishing Services by Elsevier B.V. This is an open access article under the CC BY-NC-ND license
(http://creativecommons.org/licenses/by-nc-nd/4.0/).

Please cite this article in press as: S.T. Bhangale, M.M. Pawar, Isolate and independent domination number of some classes of graphs, AKCE International Journal of Graphs and
Combinatorics (2018), https://doi.org/10.1016/j.akcej.2018.08.005.
2 S.T. Bhangale, M.M. Pawar / AKCE International Journal of Graphs and Combinatorics ( ) –

I. Sahul Hamid et al. [1] introduced the concept of Isolate domination number. A set S of vertices of a graph G
such that the induced subgraph of S denoted by ⟨S⟩ has an isolate vertex is called an isolate set of G. A dominating set
which is an isolate set is called an isolate dominating set. The minimum (maximum) cardinality of isolate dominating
set is called the isolate domination number (upper isolate domination number) and it is denoted by γ0 (G)(Γ0 (G)). In
the same paper they study irredundance number ir (G) (upper irredundance number I R(G)) and compare different
domination parameters as follows,

Proposition 1.1 ([1]). For any graph G, we have

ir (G) ≤ γ (G) ≤ γ0 (G) ≤ γi (G) ≤ β0 (G) ≤ Γ0 (G) ≤ Γ (G) ≤ I R(G).
For any positive integer n, let Z n = {0, 1, 2, . . . , n − 1} be the residue classes modulo n and ⊕ denote addition
modulo n. Then (Z n , ⊕) is an abelian group of order n. A function φ : N → N , defined as φ(n) = the number of
positive integers less than n and relatively prime to n, is called the Euler Totient function.
For a positive integer n, let S denote the set of all positive integers less than n and relatively prime to n then, the
Euler Totient Cayley Graph denoted by G(Z n , φ), is defined as the graph whose vertex set V is given by Z n and the
edge set is E = {(x, y) : x − y ∈ S or y − x ∈ S}. The concept has been introduced by Madhavi [2] and established
that the Euler Totient Cayley Graph G(Z n , φ) is simple, connected, φ(n) - regular and has nφ(n) 2
edges. It is always
Hamiltonian, Eulerian for n ≥ 3, bipartite if n is even and complete if n is prime. The domination parameters of
Euler Totient Cayley Graph are also studied by [3,4] and [5]. Uma Maheswari and B. Maheswari [5] proved following
result.
α α α
Theorem 1.2 ([5]). If n = p1 1 p2 2 . . . pk k , k ≥ 2, then the independent domination number of G(Z n , φ) is n
pk
.
In this paper we provide a counter example which disprove this result and new results for independent and isolate
domination are established. Before that in the next section we prove that for the Arithmetic graph, Cocktail party
graph, Crown and Barbell graph the domination number coincides with isolate and independent domination numbers.
In this paper all graphs considered are finite, undirected and simple graphs. For undefined terms and notations see D.
B. West [8].

2. Some graphs with γ = γ0 = γi

α α α
Let n be a positive integer with prime factorization n = p1 1 p2 2 .... pk k . The Arithmetic graph Vn is defined as the
graph whose vertex set consists of the divisors of n and two vertices u, v are adjacent in Vn if and only if the G.C.D.
(u, v) = pi , for some prime divisor pi of n. The vertex 1 becomes an isolated vertex and as the contribution of this
isolated vertex is nothing when the properties of these graphs and some domination parameters are studied, hence
Arithmetic graph Vn is considered without vertex 1.
Clearly Vn is a connected graph. If n is prime, then the graph Vn consists of a single vertex and in other cases, by
the definition of adjacency in Vn , there exist edges between prime number vertices, their prime power vertices and also
their prime product vertices. Therefore each vertex of Vn is connected to some vertex in Vn . This graph is denoted by
G(Vn ). This concept of Arithmetic graph is introduced by Vasumati [6]. Regarding Arithmetic graph Uma Maheswari
et al. [5,7] established following results.
α α α
Theorem 2.1 ([7]). If n = p1 1 p2 2 · · · pk k , where p1 , p2 , . . . , pk are primes and α1 , α2 , . . . , αk are integers ≥ 1, then
the domination number of G(Vn ) is given by
if αi = 1 for more than one i.
{
k−1
γ (G(Vn )) =
k otherwise.
where k is core of n.
α α α
Theorem 2.2 ([5]). If n = p1 1 p2 2 · · · pk k , where p1 , p2 , . . . , pk are primes and α1 , α2 , . . . , αk are integers ≥ 1, then
the independent domination number of G(Vn ) is given by
if αi = 1 for more than one i.
{
k−1
γi (G(Vn )) =
k otherwise.
where k is core of n.

Please cite this article in press as: S.T. Bhangale, M.M. Pawar, Isolate and independent domination number of some classes of graphs, AKCE International Journal of Graphs and
Combinatorics (2018), https://doi.org/10.1016/j.akcej.2018.08.005.
S.T. Bhangale, M.M. Pawar / AKCE International Journal of Graphs and Combinatorics ( ) – 3

From Proposition 1.1, Theorems 2.1 and 2.2 we conclude the following.
α α α
Theorem 2.3. If n = p1 1 p2 2 · · · pk k , where p1 , p2 , . . . , pk are primes and α1 , α2 , . . . , αk are integers ≥ 1, then the
isolate domination number of G(Vn ) is given by
if all αi > 1 or exactly one αi is 1.
{
k
γ0 (G(Vn )) =
k−1 if αi = 1 for more than one i.
where k is core of n.
Cocktail Party Graph denoted by K n×2 , is a graph having the vertex set V = ∪i=1 n
{u i , vi } where u i and vi are
vertices of two copies of kn . The edge set E = {u i u j , vi v j : i ̸= j} ∪ {u i v j , vi u j : 1 ≤ i < j ≤ n}.

Theorem 2.4. The isolate domination number of Cocktail Party graph is 2.

Proof. By definition, for any integer i the pair of vertices {u i , vi } forms a minimum dominating set which is isolate
set as well as independent set. Therefore γ (K n×2 ) = γi (K n×2 ) = γ0 (K n×2 ) = 2. ■

Crown: For an integer n ≥ 2, Crown denoted by Sn0 is the graph with vertex set {u 1 , u 2 , . . . , u n , v1 , v2 , . . . , vn } and
the edge set {u i v j : 1 ≤ i, j ≤ n, i ̸= j}. Sn0 coincides with the complete bipartite graph K n,n with the horizontal
edges removed.

Theorem 2.5. The isolate domination number of Crown graph Sn0 is 2.

Proof. Sn0 coincides with the complete bipartite graph K n,n with the horizontal edges removed. Therefore any pair of
vertices {u i , vi }, 1 ≤ i ≤ n forms a minimum dominating set which is isolate set as well as independent set. Therefore
γ (Sn0 ) = γ0 (Sn0 ) = γi (Sn0 ) = 2. ■

Barbell graph: An n-barbell graph is the simple graph obtained by connecting two copies of a complete graph K n by
a bridge.

Theorem 2.6. The isolate domination number of Barbell graph is 2.

Proof. Barbell graph G is the graph with vertex set {u 1 , u 2 , . . . , u n , v1 , v2 , . . . , vn } and the edge set {u i u j , vi v j :
1 ≤ i, j ≤ n} ∪ {(u n , vn )}. Therefore any pair of vertices {u i , v j }, 1 ≤ i, j ≤ n but not both n forms a minimum
dominating set which is isolate as well as independent. Hence, γ (G) = γ0 (G) = γi (G) = 2. ■

Note: For a graph G

(1) if γ (G) = γi (G) = 2, then by Proposition 1.1, γ (G) = γ0 (G) = γi (G) = 2.

(2) if γ (G) = γ0 (G) = 2 then a γ0 (G)-set is also γi (G)-set and hence γ (G) = γ0 (G) = γi (G) = 2.

It is interesting to note that, if γ0 (G) = γi (G) = 2, then γ (G) need not be 2.

Example 2.7. For graph K 1,2 , γ0 (K 1,2 ) = γi (K 1,2 ) = 2 but γ (K 1,2 ) = 1.

3. On Euler Totient Cayley graph

In the previous section we considered some of the graphs in which the independent domination number coincides
with the isolate domination number. In this section we compute the isolate domination number for Euler Totient
Cayley graph G(Z n , φ) with some restrictions on n.

Theorem 3.1. For n > 1, the isolate domination number of G(Z n , φ) is 1, if and only if n is prime.

Please cite this article in press as: S.T. Bhangale, M.M. Pawar, Isolate and independent domination number of some classes of graphs, AKCE International Journal of Graphs and
Combinatorics (2018), https://doi.org/10.1016/j.akcej.2018.08.005.
4 S.T. Bhangale, M.M. Pawar / AKCE International Journal of Graphs and Combinatorics ( ) –

Proof. Let n be a prime number, then G(Z n , φ) is a complete graph and hence γ0 (G(Z n , φ)) = 1.
Conversely, suppose γ0 (G(z n , φ)) = 1, let {a} be an isolate domination set of G(Z n , φ) then a is adjacent to all
other n − 1 elements in Z n i.e. d(a) = n − 1 = φ(n) and hence n is a prime. ■

Example 3.2. Consider a graph G(Z 30 , φ). The vertex set of this graph,
V = {0, 1, 2, . . . , 29} is partitioned in to following four sets.
D = {0, 3, 5, 8}.
S = {1, 7, 11, 13, 17, 19, 23, 29},
E = {2, 4, 6, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28} and
O= {9, 15, 21, 25, 27}
Here we observe that 0 dominates the set S, 3 and 5 together dominate E, and 8 dominates O. Thus D is a
dominating set of G(Z n , φ), moreover, D is independent and hence isolate set for the graph G(Z 30 , φ). Also G(Z n , φ)
is regular of order φ(n). Therefore γ (G(Z 30 , φ)) = γo (G(Z 30 , φ)) = γi (G(Z 30 , φ)) = 4.
Uma Maheswari and B. Maheswari [5] proved Theorem 1.2 As n = 30 = 2 × 3 × 5, according to above result
γi (G(Z n , φ)) = pnk = 30
5
= 6. But Example 3.2 indicates that it is not true. This fact disproves the result given in [5].
This counter example motivated us to study independent domination and isolate domination parameters for Euler
Totient Cayley graph. As a result, we establish the following.

Theorem 3.3. If n = p α , where p is prime and α ≥ 1 then

γ0 (G(Z n , φ)) = γi (G(Z n , φ)) = p α−1 .

Proof. Consider G(Z n , φ), for n = p α , where p is prime. Then the vertex set of G, V = {0, 1, 2, . . . , p α − 1} is
partitioned into the following disjoint subsets,
(1) The set S of integers relatively prime to n with cardinality φ(n).
(2) The set M of multiples of p including 0 with cardinality p α−1 .
Let s ∈ S and m ∈ M, then s dominates all elements in M and m dominates all elements in S. Thus the set
{s, m} becomes minimum dominating set but not isolate set. Also, for n > 2, G(Z n , φ) is not complete. Hence
γ (G(Z n , φ)) = 2
So no isolate domination set contains elements of S and M simultaneously. Hence M and S are the only minimal
isolate dominating sets and |M| < |S|. Also, they are the only independent dominating sets Thus γ0 (G(Z n , φ)) =
γi (G(Z n , φ)) = |M| = p α−1 . ■

Theorem 3.4. For a prime p, γ0 (G(Z 2 p , φ)) = γi (G(Z 2 p , φ)) = 2.

Proof. Consider the Euler Totient Cayley Graph G(Z 2 p , φ), where p is prime. Then the vertex set of G, V =
{0, 1, 2, . . . , 2 p − 1} can be partitioned in the following three disjoint subsets,
(1) The set S of odd integers and relatively prime to n.
(2) The set M of nonzero even numbers.
(3) The set D = {0, p}.
0 dominates all elements in S and p dominates all elements in M. Thus D is a dominating set and it is also an isolate
set. so γo (G(Z 2 p , φ)) ≤ 2. As 2 p is not prime, by Theorem 3.1 we have γ0 (G(Z 2 p , φ)) = 2. Moreover, D is also an
independent set. Thus γ (G(Z 2 p , φ)) = γo (G(Z 2 p , φ)) = γi (G(Z 2 p , φ)) = 2. ■

Theorem 3.5. If n = pq, where p < q are distinct primes greater than 2, then the isolate domination number
γ0 (G(Z n , φ)) = 3 and independent domination number γi (G(Z n , φ)) = p.

Proof. Let n = pq, where 2 < p < q are distinct primes. Then the vertex set V = {0, 1, 2, . . . , pq − 1} of G(Z n , φ)
can be partitioned as follows,

Please cite this article in press as: S.T. Bhangale, M.M. Pawar, Isolate and independent domination number of some classes of graphs, AKCE International Journal of Graphs and
Combinatorics (2018), https://doi.org/10.1016/j.akcej.2018.08.005.
S.T. Bhangale, M.M. Pawar / AKCE International Journal of Graphs and Combinatorics ( ) – 5

(1) S ⊂ Z n be the set of all integers relatively prime to n,

(2) M1 ⊂ Z n is the set of positive multiples of p,
(3) M2 ⊂ Z n is the set of positive multiples of q,
(4) Singleton set {0}.
Now 0 dominates all the vertices in set S and itself. As ( p, q) = 1, there exists α, β ∈ Z such that αp + βq = 1.
Hence, no single element in S dominates all elements in M1 ∪ M2 . Any vertex u ∈ M1 dominates all the vertices
of M2 ∪ {u} but no element of M1 − {u}. Also any vertex v ∈ M2 dominates all the vertices of M1 but no vertex of
M2 − {v}. Therefore, γ (Z n , φ) ≥ 3.
Also D = {0, p, q} is the minimum dominating set. Moreover, since (0, p) = p ̸∈ S and (0, q) = q ̸∈ S. Therefore
D = {0, p, q} is the minimum isolate dominating set. Thus γ0 (G(Z n , φ)) = 3.
It is interesting to note that, q − p ∈ S, hence D is not an independent set. An independent set of G(Z n , φ) is
dominating set only when it is maximal independent set. For an element r ∈ Z pq maximal independent sets containing
r are either {r, r + p, r + 2 p, . . . , r + (q − 1) p} or {r, r + q, r + 2q, . . . , r + ( p − 1)q}. Hence γi (G(Z n , φ)) =
p. ■

Theorem 3.6. If n = p α q β , where p and q are distinct primes but n ̸= 2 p and α, β ≥ 1 then γ0 (G(Z n , φ)) ≤
p α−1 q β−1 + 2.

Proof. Consider the Euler Totient Cayley Graph G(Z n , φ) where n = p α q β , p and q are distinct primes and α, β ≥ 1
then the vertex set of G, V = {0, 1, 2, . . . , p α q β − 1} can be divided into following disjoint subsets,
(1) S is the set of all relatively prime integers to n.
(2) M1 is the set of multiples of p but not multiples of q.
(3) M2 is the set of multiples of q but not multiples of p.
(4) M3 is the multiples of pq of cardinality p α−1 q β−1 − 1.
(5) Singleton set {0}.
Now the vertex 0 dominates all the elements of S and itself. And the vertex p ∈ M1 dominates all the vertices of M2
and the vertex q ∈ M2 dominates all the vertices of M1 . The vertices of M3 are adjacent to only vertices of S. So to
keep isolate condition on 0, we take all vertices of M3 as M3 is independent set. Therefore {0, p, q} ∪ M3 is minimum
isolate dominating set.
Thus γ0 (G(Z n , φ)) ≤ p α−1 q β−1 + 2. ■

Theorem 3.7. If n = 2 pq, where p and q are distinct primes greater than 2 then γ (G(Z n , φ)) = γ0 (G(Z n , φ)) =
γi (G(Z n , φ)) = 4.

Proof. Consider the Euler Totient Cayley Graph G(Z n , φ) where n = 2 pq, p and q are distinct primes greater than
2. Partition the vertex set of G, V = {0, 1, 2, . . . , 2 pq − 1} as,
(1) S is the set of integers less than n and relatively prime to n.
(2) E is the set of multiples of 2 except 0 and p + q.
(3) O is the set of integers in V which are either multiples of p and/or multiples of q except p and q.
(4) D = {0, p, q, p + q}.
Now the vertex 0 dominates all the vertices in S and itself. And the vertex q dominates all even integers in E except
the multiples of q but now p dominates even integers which are multiples of q. Thus { p, q} dominates all the vertices
in E and itself.
Let x ∈ O therefore x = pm or x = qn where m, n are odd integers. Let x = pm. But x − ( p + q) = p(m − 1) − q
is an odd integer which is not divisible by p or q. Therefore x − ( p + q) ∈ S. Also if x = qn, x − ( p + q) ∈ S. Thus
p + q dominates all the vertices in O and itself. Thus D = {0, p, q, p + q} becomes dominating set.
As G(Z n , φ) is φ(n)-regular graph, at least φ(n)+1
n
> 3 vertices are needed to form isolate dominating set of graph
G(Z n , φ). Therefore D = {0, p, q, p + q} is dominating set with minimum cardinality, which is isolate set as well as
independent set. Therefore γ (G(Z n , φ)) = γ0 (G(Z n , φ)) = γi (G(Z n , φ)) = 4. ■

Please cite this article in press as: S.T. Bhangale, M.M. Pawar, Isolate and independent domination number of some classes of graphs, AKCE International Journal of Graphs and
Combinatorics (2018), https://doi.org/10.1016/j.akcej.2018.08.005.
6 S.T. Bhangale, M.M. Pawar / AKCE International Journal of Graphs and Combinatorics ( ) –

References
[1] I.S. Hamid, S. Balamurugam, Isolate domination in graphs, Arab. J. Math. Sci. 22 (2015) 232–241.
[2] L. Madhavi, Studies on Domination Parameters and Enumeration of Cycles in Some Arithmetic Graphs (Ph.D. thesis), S.V. University, Tirupti,
India, 2002.
[3] S. Uma Maheswari, Some Studies on the Product Graphs of Euler Totient Cayley Graphs and Arithmetic Vn Graphs (Ph.D. thesis), S.P.
Women’s University, Tirupati, India, 2012.
[4] S. Uma Maheswari, B. Maheswari, Domination parameters of Euler Totient Cayley graphs, Rev. Bull. Cal. Math. Soc. 19 (2) (2011) 207–214.
[5] S. Uma Maheswari, B. Maheswari, Independant domination number of Euler Totient Cayley graphs and arithmetic graph, Int. J. Adv. Res. Eng.
Technol. 7 (3) (2016) 56–65.
[6] N. Vasumati, Number Theoretic Graphs (Ph.D. thesis), S.V. University, Tirupati, India, 1994.
[7] S. Uma Maheswari, B. Maheswari, Some domination parameters of Arithmetic graph Vn , ISOR J. Math. (ISSN: 2278-5728) 2 (6) (2012)
14–18.
[8] D.B. West, Introduction to Graph Theory, second ed., Pearson Education, Inc., New Jersey, 2001.

Please cite this article in press as: S.T. Bhangale, M.M. Pawar, Isolate and independent domination number of some classes of graphs, AKCE International Journal of Graphs and
Combinatorics (2018), https://doi.org/10.1016/j.akcej.2018.08.005.

View publication stats