Isolate and independent domination number of some classes of graphs

Peer review under responsibility of Kalasalingam University.

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.

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\in V\left(G\right)-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 $\gamma \left(G\right)\left(\Gamma \left(G\right)\right)$. 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 ${\gamma }_i\left(G\right)$ or $i\left(G\right)$. Upper independent domination number is denoted by ${\beta }_0\left(G\right).$

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 ${\gamma }_0\left(G\right)\left({\Gamma }_0\left(G\right)\right)$. In the same paper they study irredundance number $ir\left(G\right)$ (upper irredundance number $IR\left(G\right)$) and compare different domination parameters as follows,

Proposition 1.1

[1]

For any graph $G$, we have $ir\left(G\right)\le \gamma \left(G\right)\le {\gamma }_0\left(G\right)\le {\gamma }_i\left(G\right)\le {\beta }_0\left(G\right)\le {\Gamma }_0\left(G\right)\le \Gamma \left(G\right)\le IR\left(G\right).$

For any positive integer $n$, let $Z_n=0,1,2,\dots ,n-1$ be the residue classes modulo $n$ and $\oplus$ denote addition modulo n. Then $(Z_n,\oplus )$ is an abelian group of order $n$. A function $\varphi :N\to N$, defined as $\varphi \left(n\right)$ $=$ 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,\varphi ),$ is defined as the graph whose vertex set $V$ is given by $Z_n$ and the edge set is $E=(x,y):x-y\in Sory-x\in S$. The concept has been introduced by Madhavi [2] and established that the Euler Totient Cayley Graph $G(Z_n,\varphi )$ is simple, connected, $\varphi \left(n\right)$ - regular and has $\frac{n\varphi \left(n\right)}{2}$ edges. It is always Hamiltonian, Eulerian for $n\ge 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=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}$, $k\ge 2$, then the independent domination number of $G(Z_n,\varphi )$ is $\frac{n}{p_k}$.

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 $\gamma ={\gamma }_0={\gamma }_i$

Let $n$ be a positive integer with prime factorization $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}....p_k^{{\alpha }_k}$. The Arithmetic graph $V_n$ is defined as the graph whose vertex set consists of the divisors of $n$ and two vertices $u,v$ are adjacent in $V_n$ if and only if the G.C.D. $(u,v)=p_i$, for some prime divisor $p_i$ 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 $V_n$ is considered without vertex $1$.

Clearly $V_n$ is a connected graph. If $n$ is prime, then the graph $V_n$ consists of a single vertex and in other cases, by the definition of adjacency in $V_n$, there exist edges between prime number vertices, their prime power vertices and also their prime product vertices. Therefore each vertex of $V_n$ is connected to some vertex in $V_n$. This graph is denoted by $G\left(V_n\right)$. 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=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$, where $p_1,p_2,\dots ,p_k$ are primes and ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ are integers $\ge$ 1, then the domination number of $G\left(V_n\right)$ is given by $\gamma \left(G\left(V_n\right)\right)= \begin{array}{cc}k-1\hfill & \text{if}{\alpha }_i=1\text{for more than one}i.\hfill \\ k\hfill & \text{otherwise}.\hfill \end{array}$where $k$ is core of $n$.

Theorem 2.2

[5]

If $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$, where $p_1,p_2,\dots ,p_k$ are primes and ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ are integers $\ge$ 1, then the independent domination number of $G\left(V_n\right)$ is given by ${\gamma }_i\left(G\left(V_n\right)\right)= \begin{array}{cc}k-1\hfill & \text{if}{\alpha }_i=1\text{for more than one}i.\hfill \\ k\hfill & \text{otherwise}.\hfill \end{array}$where $k$ is core of $n$.

From Proposition 1.1, Theorems 2.1 and 2.2 we conclude the following.

Theorem 2.3

If $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$, where $p_1,p_2,\dots ,p_k$ are primes and ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ are integers $\ge$ 1, then the isolate domination number of $G\left(V_n\right)$ is given by ${\gamma }_0\left(G\left(V_n\right)\right)= \begin{array}{cc}k\hfill & \text{if all}{\alpha }_i>1\text{or exactly one}{\alpha }_i\text{is}1.\hfill \\ k-1\hfill & \text{if}{\alpha }_i=1\text{for more than one}i.\hfill \end{array}$where $k$ is core of $n$.

Cocktail Party Graph denoted by $K_{n\times 2}$, is a graph having the vertex set $V={\cup }_{i=1}^n{u}_i,v_i$ where $u_i$ and $v_i$ are vertices of two copies of $k_n$. The edge set $E=u_i{u}_j,v_i{v}_j:i\ne j\cup u_i{v}_j,v_i{u}_j:1\le i<j\le 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,v_i$ forms a minimum dominating set which is isolate set as well as independent set. Therefore $\gamma \left(K_{n\times 2}\right)={\gamma }_i\left(K_{n\times 2}\right)={\gamma }_0\left(K_{n\times 2}\right)=2$. □

Crown: For an integer $n\ge 2$, Crown denoted by $S_n^0$ is the graph with vertex set $u_1,u_2,\dots ,u_n,v_1,v_2,\dots ,v_n$ and the edge set $u_i{v}_j:1\le i,j\le n,i\ne j$. $S_n^0$ coincides with the complete bipartite graph $K_{n,n}$ with the horizontal edges removed.

Theorem 2.5

The isolate domination number of Crown graph $S_n^0$ is $2$.

Proof

$S_n^0$ coincides with the complete bipartite graph $K_{n,n}$ with the horizontal edges removed. Therefore any pair of vertices $u_i,v_i,1\le i\le n$ forms a minimum dominating set which is isolate set as well as independent set. Therefore $\gamma \left(S_n^0\right)={\gamma }_0\left(S_n^0\right)={\gamma }_i\left(S_n^0\right)=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,\dots ,u_n,v_1,v_2,\dots ,v_n$ and the edge set $u_i{u}_j,v_i{v}_j:1\le i,j\le n\cup (u_n,v_n)$. Therefore any pair of vertices $u_i,v_j,1\le i,j\le n$ but not both $n$ forms a minimum dominating set which is isolate as well as independent. Hence, $\gamma \left(G\right)={\gamma }_0\left(G\right)={\gamma }_i\left(G\right)=2$. □

Note: For a graph $G$

(1)	if $\gamma \left(G\right)={\gamma }_i\left(G\right)=2$, then by Proposition 1.1, $\gamma \left(G\right)={\gamma }_0\left(G\right)={\gamma }_i\left(G\right)=2$.

(2)	if $\gamma \left(G\right)={\gamma }_0\left(G\right)=2$ then a ${\gamma }_0\left(G\right)$-set is also ${\gamma }_i\left(G\right)$-set and hence $\gamma \left(G\right)={\gamma }_0\left(G\right)={\gamma }_i\left(G\right)=2$.

It is interesting to note that, if ${\gamma }_0\left(G\right)={\gamma }_i\left(G\right)=2$, then $\gamma \left(G\right)$ need not be $2$.

Example 2.7

For graph $K_{1,2}$, ${\gamma }_0\left(K_{1,2}\right)={\gamma }_i\left(K_{1,2}\right)=2$ but $\gamma \left(K_{1,2}\right)=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,\varphi )$ with some restrictions on $n$.

Theorem 3.1

For $n>1$, the isolate domination number of $G(Z_n,\varphi )$ is $1$, if and only if $n$ is prime.

Proof

Let $n$ be a prime number, then $G(Z_n,\varphi )$ is a complete graph and hence ${\gamma }_0\left(G(Z_n,\varphi )\right)=1.$

Conversely, suppose ${\gamma }_0\left(G(z_n,\varphi )\right)=1$, let $a$ be an isolate domination set of $G(Z_n,\varphi )$ then $a$ is adjacent to all other $n-1$ elements in $Z_n$ i.e. $d\left(a\right)=n-1=\varphi \left(n\right)$ and hence $n$ is a prime. □

Example 3.2

Consider a graph $G(Z_{30},\varphi )$. The vertex set of this graph,

$V=0,1,2,\dots ,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,\varphi )$, moreover, $D$ is independent and hence isolate set for the graph $G(Z_{30},\varphi )$. Also $G(Z_n,\varphi )$ is regular of order $\varphi \left(n\right)$. Therefore $\gamma \left(G(Z_{30},\varphi )\right)={\gamma }_o\left(G(Z_{30},\varphi )\right)={\gamma }_i\left(G(Z_{30},\varphi )\right)=4$.

Uma Maheswari and B. Maheswari [5] proved Theorem 1.2 As $n=30=2\times 3\times 5,$ according to above result ${\gamma }_i\left(G(Z_n,\varphi )\right)=\frac{n}{p_k}=\frac{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^{\alpha }$, where $p$ is prime and $\alpha \ge 1$ then ${\gamma }_0\left(G(Z_n,\varphi )\right)={\gamma }_i\left(G(Z_n,\varphi )\right)=p^{\alpha -1}.$

Proof

Consider $G(Z_n,\varphi )$, for $n=p^{\alpha }$, where $p$ is prime. Then the vertex set of $G$, $V=0,1,2,\dots ,p^{\alpha }-1$ is partitioned into the following disjoint subsets,

(1)	The set $S$ of integers relatively prime to $n$ with cardinality $\varphi \left(n\right)$.

(2)	The set $M$ of multiples of $p$ including $0$ with cardinality $p^{\alpha -1}$.

Let $s\in S$ and $m\in 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,\varphi )$ is not complete. Hence $\gamma \left(G(Z_n,\varphi )\right)=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 ${\gamma }_0\left(G(Z_n,\varphi )\right)={\gamma }_i\left(G(Z_n,\varphi )\right)=M=p^{\alpha -1}$. □

Theorem 3.4

For a prime $p$, ${\gamma }_0\left(G(Z_{2p},\varphi )\right)={\gamma }_i\left(G(Z_{2p},\varphi )\right)=2.$

Proof

Consider the Euler Totient Cayley Graph $G(Z_{2p},\varphi )$, where $p$ is prime. Then the vertex set of $G$, $V=0,1,2,\dots ,2p-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 ${\gamma }_o\left(G(Z_{2p},\varphi )\right)\le 2$. As $2p$ is not prime, by Theorem 3.1 we have ${\gamma }_0\left(G(Z_{2p},\varphi )\right)=2$. Moreover, $D$ is also an independent set. Thus $\gamma \left(G(Z_{2p},\varphi )\right)={\gamma }_o\left(G(Z_{2p},\varphi )\right)={\gamma }_i\left(G(Z_{2p},\varphi )\right)=2$. □

Theorem 3.5

If $n=pq$, where $p<q$ are distinct primes greater than 2, then the isolate domination number ${\gamma }_0\left(G(Z_n,\varphi )\right)=3$ and independent domination number ${\gamma }_i\left(G(Z_n,\varphi )\right)=p$.

Proof

Let $n=pq$, where $2<p<q$ are distinct primes. Then the vertex set $V=0,1,2,\dots ,pq-1$ of $G(Z_n,\varphi )$ can be partitioned as follows,

(1)	$S\subset Z_n$ be the set of all integers relatively prime to $n$,

(2)	$M_1\subset Z_n$ is the set of positive multiples of $p$,

(3)	$M_2\subset 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 $\alpha ,\beta \in Z$ such that $\alpha p+\beta q=1.$ Hence, no single element in $S$ dominates all elements in $M_1\cup M_2$. Any vertex $u\in M_1$ dominates all the vertices of $M_2\cup u$ but no element of $M_1-u$. Also any vertex $v\in M_2$ dominates all the vertices of $M_1$ but no vertex of $M_2-v.$ Therefore, $\gamma (Z_n,\varphi )\ge 3.$

Also $D=0,p,q$ is the minimum dominating set. Moreover, since $(0,p)=p\notin S$ and $(0,q)=q\notin S$. Therefore $D=0,p,q$ is the minimum isolate dominating set. Thus ${\gamma }_0\left(G(Z_n,\varphi )\right)=3$.

It is interesting to note that, $q-p\in S$, hence $D$ is not an independent set. An independent set of $G(Z_n,\varphi )$ is dominating set only when it is maximal independent set. For an element $r\in Z_{pq}$ maximal independent sets containing $r$ are either $r,r+p,r+2p,\dots ,r+(q-1)p$ or $r,r+q,r+2q,\dots ,r+(p-1)q$. Hence ${\gamma }_i\left(G(Z_n,\varphi )\right)=p.$ □

Theorem 3.6

If $n=p^{\alpha }{q}^{\beta }$, where $p$ and $q$ are distinct primes but $n\ne 2p$ and $\alpha ,\beta \ge 1$ then ${\gamma }_0\left(G(Z_n,\varphi )\right)\le p^{\alpha -1}{q}^{\beta -1}+2$.

Proof

Consider the Euler Totient Cayley Graph $G(Z_n,\varphi )$ where $n=p^{\alpha }{q}^{\beta }$, $p$ and $q$ are distinct primes and $\alpha ,\beta \ge 1$ then the vertex set of $G$, $V=0,1,2,\dots ,p^{\alpha }{q}^{\beta }-1$ can be divided into following disjoint subsets,

(1)	$S$ is the set of all relatively prime integers to $n$.

(2)	$M_1$ is the set of multiples of $p$ but not multiples of $q$.

(3)	$M_2$ is the set of multiples of $q$ but not multiples of $p$.

(4)	$M_3$ is the multiples of $pq$ of cardinality $p^{\alpha -1}{q}^{\beta -1}-1$.

(5)	Singleton set 0 .

Now the vertex $0$ dominates all the elements of $S$ and itself. And the vertex $p\in M_1$ dominates all the vertices of $M_2$ and the vertex $q\in M_2$ dominates all the vertices of $M_1$. The vertices of $M_3$ are adjacent to only vertices of $S$. So to keep isolate condition on $0$, we take all vertices of $M_3$ as $M_3$ is independent set. Therefore $0,p,q\cup M_3$ is minimum isolate dominating set.

Thus ${\gamma }_0\left(G(Z_n,\varphi )\right)\le p^{\alpha -1}{q}^{\beta -1}+2$. □

Theorem 3.7

If $n=2pq$, where $p$ and $q$ are distinct primes greater than $2$ then $\gamma \left(G(Z_n,\varphi )\right)={\gamma }_0\left(G(Z_n,\varphi )\right)={\gamma }_i\left(G(Z_n,\varphi )\right)=4$.

Proof

Consider the Euler Totient Cayley Graph $G(Z_n,\varphi )$ where $n=2pq$, $p$ and $q$ are distinct primes greater than 2. Partition the vertex set of $G$, $V=0,1,2,\dots ,2pq-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\in 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)\in S$. Also if $x=qn$, $x-(p+q)\in 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,\varphi )$ is $\varphi \left(n\right)$-regular graph, at least $\frac{n}{\varphi \left(n\right)+1}>3$ vertices are needed to form isolate dominating set of graph $G(Z_n,\varphi )$. Therefore $D=0,p,q,p+q$ is dominating set with minimum cardinality, which is isolate set as well as independent set. Therefore $\gamma \left(G(Z_n,\varphi )\right)={\gamma }_0\left(G(Z_n,\varphi )\right)={\gamma }_i\left(G(Z_n,\varphi )\right)=4.$ □

Notes

Peer review under responsibility of Kalasalingam University.