Domination in Cayley graphs: A survey

Peer review under responsibility of Kalasalingam University.

Abstract

Let $\Omega$ be a symmetric generating set of a finite group $\Gamma$. Assume that $(\Gamma ,\Omega )$ be such that $\Gamma =〈\Omega 〉$ and $\Omega$ satisfies the two conditions $C_1$: the identity element $e\notin \Omega$ and $C_2$: if $a\in \Omega$, then $a^{-1}\in \Omega .$ Given $(\Gamma ,\Omega )$ satisfying $C_1$ and $C_2,$ define a Cayley graph $G=Cay(\Gamma ,\Omega )$ with $V\left(G\right)=\Gamma$ and $E\left(G\right)={(x,y)}_{a}x,y\in \Gamma ,a\in \Omega \mathrm{and}y=xa$. When $\Gamma ={\mathbb{Z}}_n=〈\Omega 〉$, it is called as circulant graph and denoted by $Cir(n,\Omega )$. In this paper, we give a survey about the results on dominating sets in Cayley graphs and circulant graphs.

Keywords:

• Cayley graph
• Unitary Cayley graph
• Dominating sets
• Efficient dominating sets
• E-Chain

1 Introduction

The concept of Cayley graph plays a vital role in dealing with certain optimization problems, especially routing problems in interconnection networks of a parallel computer. Parallel processing and super computing continue to exert great influence in the development of modern science and engineering. The network comprising of processors plays a vital role in facilitating the communication between processors in a computer system. Some of the popular interconnection schemes are rings, torus and hypercubes. Their popularity stems from the commercial availability of machines with these architectures. These three families of graphs – rings, torus and hypercube – share a common property of being a Cayley graph. Many important problems in networks have been modeled by Cayley graphs. Since Cayley graphs have the property of vertex transitivity, it is possible to implement routing and communication schemes at each node of the network. One of the principal issues concerning routing problems is identification of perfect dominating sets in Cayley graphs. This will help in identifying optimal substructures in order to facilitate the communication between processors.

Cayley graph is a discrete structure created out of groups, more specifically from a finite group $\Gamma$ and its generating set $\Omega .$ A non-empty subset $\Omega \subset \Gamma$ is called a generating set for $\Gamma$, denoted by $\Gamma =〈\Omega 〉$, if every element of $\Gamma$ can be expressed as a product of elements in $\Omega$. For a generating set $\Omega$ of $\Gamma$, we assume that

$C_1$: The identity element $e\notin \Omega$ and $C_2$: If $a\in \Omega$, then $a^{-1}\in \Omega$.

The concept of domination in graphs appears as a natural model for facility location problems, and has many applications in design and analysis of communication networks, network routing and coding theory, among others [1]. Another application of dominating sets is broadcasting in wormhole-routed networks. Dominating sets have many uses in design theory and efficient use in computer networks. They can be used to decide the placement of limited resources so that every node has access to the resources locally or through a neighboring node. A minimum dominating set provides this access to resources at minimum cost. The most efficient solution is one that avoids duplication of access to the resources. This more restricted version of minimum dominating set is called an independent perfect or efficient dominating set. For basic definitions and results concerning domination in graphs, one can refer to [1]. In this paper, we make a survey of results connecting the domination in Cayley graphs, domination, connected domination, total domination and efficient domination on circulant graphs. Finally, we present results connecting subgroups of a group as efficient dominating sets in the corresponding Cayley graphs.

2 Domination in Cayley graphs

Even though Cayley graphs are extensively dealt in various literature, only few authors have worked on domination in Cayley graphs. To understand the concept of domination for Cayley graphs, one can refer to [2–6^{[2][3][4][5][6]}]. Lee [6] has studied the efficient dominating sets in Cayley graphs using covering projections. He obtained a necessary and sufficient condition for the existence of an efficient dominating set in a Cayley graph. As an application, he classified the hypercubes which admit efficient dominating sets. In this section, we present results related to domination in Cayley graphs.

Lemma 2.1

[6, Lemma 1]

(a)	Let $S_1$ and $S_2$ be two independent perfect dominating sets of a graph $G$. Then $S_1=S_2$.

(b)	Let $S_1,\dots ,S_n$ be $n$ independent perfect dominating sets of a graph $G$ which are pairwise mutually disjoint. Then the subgraph $H$ induced by $S_1\cup \cdots \cup S_n$ is an $m$-fold covering graph of the complete graph $K_n$, where $m=S_i$ for each $i=1,2,\dots ,n$.

Lemma 2.2

[6, Lemma 2]

Let $p:\tilde{G}\to G$ be a covering and let $S$ be a perfect dominating set of $G$. Then $p^{-1}\left(S\right)$ is a perfect dominating set of $\tilde{G}$. Moreover, if $S$ is independent, then $p^{-1}\left(S\right)$ is independent.

Theorem 2.3

[6, Theorem 1]

Let $G$ be a graph and let $n$ be a natural number. Then $G$ is a covering of the complete graph $K_n$ if and only if $G$ has a vertex partition $S_1,\dots ,S_n$such that $S_i$ is an independent perfect dominating set for each $i=1,2,\dots ,n$.

Lemma 2.4

[6, Lemma 3]

Let $X=x_1,\dots ,x_n$be a symmetric generating set for a group $\mathbb{A}$ and let $S$ be an independent perfect dominating set of the Cayley graph $Cay(\mathbb{A},X)$. Then

(a)	for each $i=1,2,\dots ,n$, $x_{i}S$ is an independent perfect dominating set of $Cay(\mathbb{A},X)$, and

(b)	$S,S{x}_1,\dots ,S{x}_n$forms a vertex partition of $Cay(\mathbb{A},X)$.

For a subset $S$ of a group $\mathbb{A}$, define $S^0=S\cup 0$, where $0$ is the identity element in $\mathbb{A}$.

Theorem 2.5

[6, Theorem 2]

Let $X=x_1,\dots ,x_n$be a symmetric generating set for a group $\mathbb{A}$ and let $S$ be a normal subset of $\mathbb{A}$. Then the following are equivalent.

(a)	$S$ is an independent perfect dominating set of $Cay(\mathbb{A},X)$.

(b)	There exists a covering $p:Cay(\mathbb{A},X)\to K_{X+1}$ such that $p^{-1}\left(v\right)=S$ for some $v\in V\left(K_{X+1}\right)$.

(c)	$S=\frac{\mathbb{A}}{X+1}$ and $S\cap [S+((X^{\circ }+X^{\circ })\setminus 0)]=\varnothing$.

Theorem 2.6

[6, Corollary 2]

Let $X=x_1,\dots ,x_n$be a symmetric generating set for a group $\mathbb{A}$ and let $S$ be a normal subgroup of $\mathbb{A}$. Then the following are equivalent.

(a)	$S$ is an independent perfect dominating set of $Cay(\mathbb{A},X)$.

(b)	$Cay(\mathbb{A},X)$ is an S-covering graph of the graph $K_{X+1}$.

(c)	$\mathbb{A}∕S=X+1$ and $S\cap (X^{\circ }+X^{\circ })=0$.

Theorem 2.7

[6, Theorem 3]

Let $n$ be a natural number. Then the following are equivalent.

(a)	The hypercube $Q_n$ has an independent perfect dominating set.

(b)	$n=2^m-1$ for a natural number $m$.

(c)	The hypercube $Q_n$ is a regular covering of the complete graph $K_{n+1}$.

Italo J. Dejter and Oriol Serra [2] gave a constructing tool to produce E-chains of Cayley graphs. This tool is used to construct infinite families of E-chains of Cayley graphs on symmetric groups.

Lemma 2.8

[2, Lemma 1]

Let $A$ be a generating set of a finite group $G$ such that $s^2=1$ for each $s\in A$. Let $u\in A$ be such that $A_u=A\setminus u$ generates a proper subgroup $H$ of $G$ of index $A+1$ in $G$. If $U=H\cap uHu$ is an $E$-set in $Cay(H,A_u)$, then the open neighborhood $N\left(H\right)$ of $H$ is an $E$-set in $Cay(G,A)$. Moreover, there are inclusive maps ${\varsigma }^{\left(j\right)}$ such that ${\varsigma }^{\left(j\right)}\left(U\right),j=1,\dots ,A$is a partition of the $E$-set $N\left(H\right)$.

Further, Italo J. Dejter [5] obtained a necessary and sufficient condition for the existence of an efficient open dominating set (1-perfect code) in Cartesian product of two cycles.

Theorem 2.9

[5, Theorem 7]

There exists a toroidal graph $C_m\times C_n$ having a 1-perfect code partition if and only if $m$ and $n$ are multiples of 5.

Hamed Hatami and Pooya Hatami [3] characterized the structure of perfect dominating sets in the simplest case $Cay({\mathbb{Z}}_{2n+1}^n;U)$ where $2n+1$ is a prime, $U=\pm e_1,\dots ,\pm e_n$ is the set of generators of ${\mathbb{Z}}_{2n+1}^n$ and $e_i=(0,\dots ,1,\dots ,0)$ is the unit vector with $1$ at the $i$th coordinate.

Theorem 2.10

[3, Theorem 1]

Let $2n+1$ be a prime and $S\subseteq Cay({\mathbb{Z}}_{2n+1}^n,U)$ be a perfect dominating set. Then for every $(x_1,\dots ,x_n)\in {\mathbb{Z}}_{2n+1}^n$ and every $i\in 1,\dots ,n$, $S\cap (y_1,\dots ,y_n):y_j=x_j\forall j\ne i =1$.

Circulant graphs are Cayley graphs on the simplest of groups and thus may provide direction into Cayley graphs on other groups, particularly finite groups. Any finite vertex-transitive graph of prime order is a circulant graph and hence the study of vertex transitive graphs can gain from the study of circulant graphs. Nenad Obradovič, Joseph Peters, and Ružić [7] studied the efficient domination in circulant graphs with two chord lengths. They have obtained necessary and sufficient conditions for the existence of an efficient dominating set in circulant graphs of degree 3 and 4. The following are some of the important results concerning domination in circulant graphs.

Theorem 2.11

[7, Theorem 1]

Let $G=Cir(n,S=s_1,s_2)$ be a connected 4-regular circulant graph. $G$ admits efficient domination if and only if $n=5.i,i\in \mathbb{N}$ and $s_1\pm s_2\ne 0\left(mod5\right)$ and $s_1,s_2\ne 0\left(mod5\right)$.

Theorem 2.12

[7, Theorem 2]

Let $G=Cir(n,S=s_1,s_2(=\frac{n}{2}))$ be a connected 3-regular circulant graph. $G$ admits efficient domination if and only if $n=8j+4$ for some $j\in \mathbb{N}$.

Jia Huang and Jun-Ming Xu [4] have studied the relationship between the bondage number and the efficient dominating sets of vertex-transitive graphs. Further, they have proved that some Harary graphs admit efficient dominating sets. Let $k<n$. The Harary graph $H_{k,n}$ is a graph of order $n$ and connectivity $k$ with minimum number of edges. Let $s=\frac{k}{2}$ when $k$ is even and $s=\frac{k-1}{2}$ when $k$ is odd. If $k$ is even and $A=1,2,\dots ,s,n-s,n-(s-1),\dots ,n-1$, then the corresponding circulant graph $Cir(n,A)$ is denoted by $H_{k,n}^0$ [4]. Similarly if $k$ is odd, $n$ is even and $A=1,2,\dots ,s,\frac{n}{2},n-s,n-(s-1),\dots ,n-1$, then $Cir(n,A)$ is denoted by $H_{k,n}^1$ [4].

Lemma 2.13

[4, Lemma 4.5]

$\gamma \left(H_{k,n}^0\right)=\lceil \frac{n}{k+1}\rceil .$

Lemma 2.14

[4, Lemma 4.7]

Let $G=H_{k,n}^1$. Then $G$ has an efficient dominating set if and only if $n=(k+1)p$ for an odd $p$, and all efficient dominating sets in $G$ have the form $D_i=v\in V\left(G\right):v\equiv i(modk+1)$.

Lemma 2.15

[4, Lemma 4.3]

Let $G=Cir(n;1,s)$ with $s\ne \frac{n}{2}$. Then $\lceil \frac{n}{5}\rceil \le \gamma \left(G\right)\le \lceil \frac{n}{3}\rceil$, and $G$ has an efficient dominating set if and only if $5n$ and $s\equiv \pm 2\left(mod5\right)$. In addition, all efficient dominating sets in $G$ have the form $D_i=v\in V\left(G\right):v\equiv i\left(mod5\right)$.

Tamizh Chelvam and Mutharasu [8] characterized some classes of circulant Harary graphs which admit efficient dominating sets and the same are presented below.

Lemma 2.16

[8, Lemma 9]

If $3s+1$ divides $n$, then ${\gamma }_t\left(H_{k,n}^0\right)=\frac{2n}{3s+1}$.

Theorem 2.17

[8, Theorem 10]

The graph $H_{k,n}^0$ has an efficient open dominating set if and only if $k=2$ and $4$ divides $n$.

Lemma 2.18

[8, Lemma 11]

If $4s+2$ divides $n$, then ${\gamma }_t\left(H_{k,n}^1\right)=\frac{2n}{4s+2}$.

Theorem 2.19

[8, Theorem 12]

The graph $H_{k,n}^1$ has an efficient open dominating set if and only if $4s+2$ divides $n$.

A different approach was made by Young Soo Kwon and Jaeun Lee [9] in dealing the perfect dominating sets in Cayley graphs. They show that if a Cayley graph $Cay(\mathbb{A},X)$ has a perfect dominating set $S$ which is a normal subgroup of $\mathbb{A}$ and whose induced subgraph is $F$, then there exists an $F$-bundle projection $p:Cay(\mathbb{A},X)\to K_m$ for some positive integer $m$. As an application, they studied perfect dominating sets in the hypercube $Q_n$. It is known that $Q_n$ is isomorphic to the Cayley graph $Cay({\mathbb{Z}}_2^n,X)$, where $X=e_1,e_2,\dots ,e_n$.

Theorem 2.20

[9, Theorem 7]

Let $X=x_1,\dots ,x_n$be a symmetric generating set for a group $\mathbb{A}$ and let $S$ be a normal subgroup of $\mathbb{A}$. Let $S\cap X=x_{\ell },x_{\ell +1},\dots ,x_n$ and let $\mathbb{B}$ be the subgroup generated by $S\cap X$. Let $F=S∕\mathbb{B}Cay(\mathbb{B},S\cap X)$ be the disjoint union of $S∕\mathbb{B}$ copies of the Cayley graph $Cay(\mathbb{B},S\cap X)$. Now the following are equivalent.

(a)	$S$ is an $F$-perfect dominating set of $Cay(\mathbb{A},X)$.

(b)	There exists an $F$-bundle projection $p:Cay(\mathbb{A},X)\to K_{\ell }$ such that $p^{-1}\left(v_{\ell }\right)=S$, where $K_{\ell }$ is the complete graph on $\ell$ vertices $v_1,v_2,\dots ,v_{\ell }$.

(c)	$\mathbb{A}∕S=\ell$ and $S\cap {\left(X_{\ell -1}\right)}^2=1$, where $1$ is the identity and $X_{\ell -1}=x_1,x_2,\dots ,x_{\ell -1}$, and $A^2=a{a}^{\prime }a,a^{\prime }\in A$ for any subset $A$ of $\mathbb{A}$.

Let $\mathbb{A}$ be an abelian group and let $S$ be a subgroup of $\mathbb{A}$. For any symmetric generating set $X=x_1,\dots ,x_n$ of $\mathbb{A}$, let $S\cap X=x_{\ell },x_{\ell +1},\dots ,x_n$. Let $\mathbb{B}$ be the subgroup generated by $S\cap X$ and let $\overline{X}=X∕\mathbb{B}={\overline{x}}_1,\dots ,{\overline{x}}_{\ell -1}$. Now $\overline{X}$ is a symmetric generating set for the quotient group $\mathbb{A}∕\mathbb{B}$. The following corollary comes from Theorem 2.20.

Corollary 2.21

[9, Corollary 8]

Let $X=x_1,\dots ,x_n$be a symmetric generating set for an abelian group $\mathbb{A}$ and let $S$ be a subgroup of $\mathbb{A}$. Then the following are equivalent.

(a)	$S∕\mathbb{B}$ is an efficient dominating set of $Cay(\mathbb{A}∕\mathbb{B},\overline{X})$.

(b)	There exists a regular covering projection $p:Cay(\mathbb{A}∕\mathbb{B},\overline{X})\to K_{\ell }$ such that $p^{-1}\left(v_{\ell }\right)=S∕\mathbb{B}$.

(c)	$(\mathbb{A}∕\mathbb{B})∕(S∕\mathbb{B})=\mathbb{A}∕S=\ell$ and $S∕\mathbb{B}\cap {\overline{X}}^2=\overline{1}$, where $\overline{1}$ is the identity of $\mathbb{A}∕\mathbb{B}$.

The following theorem gives several necessary and sufficient conditions for a hypercube $Q_n$ to have a perfect total dominating set.

Theorem 2.22

[9, Theorem 11]

For a positive integer $n$, the following are equivalent.

(a)	The hypercube $Q_n$ has a perfect total dominating set.

(b)	$n=2^m$ for a positive integer $m$.

(c)	The hypercube $Q_n$ is a $2^{n-lo{g}_{2}n-1}{K}_2$-bundle over the complete graph $K_n$.

(d)	The hypercube $Q_n$ is a covering of the complete bipartite graph $K_{n,n}$.

Corollary 2.23

[9, Corollary 12]

Let $m$ and $n$ be two positive integers such that $n-m+1$ is a power of $2$. Then the hypercube $Q_n$ is a $2^{n-m-lo{g}_2(n-m+1)}$ $Q_m$-bundle over the complete graph $K_{n-m+1}$ and hence has a $2^{n-m-lo{g}_2(n-m+1)}$ $Q_m$- perfect dominating set.

3 Efficient open domination in Cayley graphs

In this section, we present results in connection with bipartite Cayley graphs which admit efficient open dominating sets.

Lemma 3.1

[8, Lemma 4]

Let $X= x_1,x_2,\dots ,x_n$ be a generating set of a group $\Gamma$ and $S$ be an efficient open dominating set of $G=Cay(\Gamma ,X)$. Then we have the following:

(a)	For each $i$ with $1\le i\le n$, $x_{i}S$ is an efficient open dominating set in $G$.

(b)	$S{x}_1,S{x}_2,\dots ,S{x}_n$ is a vertex partition of $G$.

Lemma 3.2

[8, Lemma 5]

Let $S_1,S_2,\dots ,S_n$ be pairwise disjoint efficient open dominating sets of a graph $G$ and $\tilde{G}$ be the subgraph of $G$, induced by $S_1\cup S_2\cup \cdots \cup S_n$. Let $m=\frac{S_1}{2}$. If $\tilde{G}$ is bipartite, then there exists a $m$-fold covering projection from $\tilde{G}$ onto $K_{n,n}$.

From Lemmas 3.1 and 3.2, we have the following corollary.

Corollary 3.3

[8, Corollary 1]

Let $G=Cay(\Gamma ,X)$ be a bipartite Cayley graph with $X= x_1,x_2,\dots ,x_n$ and let $S$ be an efficient open dominating set of $G$. If $x_{i}S=S{x}_i$ for each $i=1,\dots ,n$, then there exists a covering projection $f:G\to K_{n,n}$ such that $S{x}_i=f^{-1}\left( y_i,z_i \right)$ for $1\le i\le n$, where $V\left(K_{n,n}\right)=(Y,Z)$ with $Y= y_1,y_2,\dots ,y_n$ and $Z= z_1,z_2,\dots ,z_n$.

Lemma 3.4

[8, Lemma 6]

Let $f:\tilde{G}\to G$ be a covering projection and $S$ be an efficient open dominating set in $G$. Then $f^{-1}\left(S\right)$ is an efficient open dominating set in $\tilde{G}$.

Theorem 3.5

[8, Theorem 7]

A graph $G$ is a covering graph of $K_{n,n}$ if and only if $G$ is bipartite and has a vertex partition $S_1,S_2,\dots ,S_n$ such that $S_i$ is an efficient open dominating set in $G$ for $1\le i\le n$.

Theorem 3.6

[8, Theorem 8]

Let $G=Cay(\Gamma ,X)$ be a bipartite Cayley graph with $X= x_1,x_2,\dots ,x_n$ and let $S$ be a normal subset of $\Gamma$ (i.e., $gS=Sg$ for all $g\in \Gamma$). Then the following are equivalent.

(a)	$S$ is an efficient open dominating set of $G$.

(b)	There exists a covering projection $f:G\to K_{n,n}$ such that $f^{-1}\left( y_i,z_i \right)=S$ for some $1\le i\le n$, where $V\left(K_{n,n}\right)=(Y,Z)$ with $Y= y_1,y_2,\dots ,y_n$ and $Z= z_1,z_2,\dots ,z_n$.

(c)	$S=\frac{\Gamma }{n}$ and $S\cap \left[S(\left(XX\right)\setminus e )\right]=\varphi$, where $e$ is the identity of $\Gamma$.

Assume that $k<n$. Consider a graph of order $n$ and connectivity $k$ with minimum number of edges. If $k$ is odd and $n$ is even, let $m=\frac{n}{2}-1$. If $X=m-(p-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(p-1))$, then $G_{k,n}$ denotes the circulant graph $Cir(n,X)$.

Lemma 3.7

[8, Lemma 13]

${\gamma }_t\left(G_{k,n}\right)=⌈\frac{n}{k}⌉$.

Theorem 3.8

[8, Theorem 14]

The graph $G_{k,n}$ has an efficient open dominating set if and only if $k$ divides $n$.

A countable family of graphs $G= {\Gamma }_1\subseteq {\Gamma }_2\subseteq \dots \subseteq {\Gamma }_i\subseteq {\Gamma }_{i+1}\subseteq \dots$ is an E-chain if every ${\Gamma }_i$ is an induced subgraph of ${\Gamma }_{i+1}$ and each ${\Gamma }_i$ has an efficient dominating set $C_i$ [2]. Dejter et al. [2] derived infinite families of E-chains in Cayley graphs constructed from symmetric groups. Using this, one can obtain an efficient dominating set for a Cayley graph of order $(n+1)!$ from an efficient dominating set of a Cayley graph of order $n!$. The difference between $n!$ and $(n+1)!$ is large and one needs to find some tool to obtain efficient dominating sets in Cayley graphs of order $t$, where $n!<t<(n+1)!$. With this in mind, Tamizh Chelvam and Mutharasu [8] constructed E-chains in circulant graphs using covering projections. Let $n$ and $p$ be positive integers with $1\le p\le \frac{n-1}{2}$. Let $X= x_1,x_2,\dots ,x_p,n-x_p,n-x_{p-1},\dots ,n-x_1 \subseteq {\mathbb{Z}}_n$ with $gcd(x_1,x_2,\dots ,x_p)=1$. Note that $X$ is a generating set of the group ${\mathbb{Z}}_n$.

Lemma 3.9

[8, Lemma 15]

Let $n,q\ge 2$ and $p\ge 1$ be integers with $1\le p\le \frac{n-1}{2}$. Let $X= x_1,x_2,\dots ,x_p,n-x_p,n-x_{p-1},\dots ,n-x_1$ and $Y= x_1,x_2,\dots ,x_p,nq-x_p,nq-x_{p-1},\dots ,nq-x_1$. Then $\tilde{G}=Cir(nq,Y)$ is a covering graph of $G=Cir(n,X)$.

By Lemmas 2.2, 3.4 and 3.9, one can have the following theorem, which gives E-chains and EO-chains in circulant graphs.

Theorem 3.10

[8, Theorem 16]

Let $n,q_i\ge 2$ be integers for $i=1,2,\dots$ and $S$ be an efficient open dominating set (or efficient dominating set) of $Cir(n,X)$, where $X= x_1,x_2,\dots ,x_p,n-x_p,n-x_{p-1},\dots ,n-x_1$. Suppose

$X_i= x_1,x_2,\dots ,x_p,n{q}_1{q}_2\dots q_i-x_p,n{q}_1{q}_2\dots q_i-x_{p-1},\dots ,n{q}_1{q}_2\dots q_i-x_1$ for $i=1,2,\dots$. Then an EO-chain (or E-chain) for the graphs $Cir(n,X)$, $Cir(n{q}_1,X_1)$, $Cir(n{q}_1{q}_2,X_2),\dots ,$ is given by $S\subset S_1\subset S_2\subset S_3\subset \dots ,$ where $S_1,S_2,\dots$ are constructed as follows:

(a)	$S_1=f_{q_1}^{-1}\left(S\right)$, where $f_{q_1}:Cir(n{q}_1,X_1)\to Cir(n,X)$ is a covering projection and

(b)	$S_i=f_{q_i}^{-1}\left(S_{i-1}\right)$, where $f_{q_i}:Cir(n{q}_1{q}_2\dots q_i,X_i)\to Cir(n{q}_1{q}_2\dots q_{i-1},X_{i-1})$ is a covering projection for each integer $i\ge 2$.

4 Domination in circulant graphs

Efficient dominating sets correspond to perfect 1-correcting codes in a network. It makes the study of dominating sets and efficient dominating sets in circulant graphs as an important one. To study about domination in circulant graphs, one may refer [4,7]. In [4], Jia Huang and Jun-Ming Xu obtained the domination number for some classes of circulant graphs. Further, they identified some classes of circulant graphs which admits an efficient dominating set. In [7], Nenad Obradovič, Joseph Peters, and Ružić studied the efficient dominating sets in circulant graphs with two chord lengths. In this section, we present results connecting domination, total domination, connected domination, perfect domination, independent domination and efficient domination numbers for some circulant graphs. The domination number depends on the elements in the generating set, and so it is very difficult to find an algorithm to obtain a $\gamma$-set for an arbitrary circulant graph. Finding the domination number for an arbitrary circulant graph is still an unsolved problem. Tamizh Chelvam, Rani and Mutharasu [81011^[12][13][14]–15] have obtained the domination number for some classes of circulant graphs. Further, they proved that the respective class of circulant graphs are 2-excellent. Unless otherwise specified, $A$ stands for the generating set $1,2,\dots ,k,n-k,n-(k-1),\dots ,n-1$ of ${\mathbb{Z}}_n$ with $1\le k\le \frac{n-1}{2}$ and $B$ stands for the generating set $1,3,\dots ,2k-1,n-(2k-1),\dots ,n-3,n-1$ with $1\le k\le \frac{n-1}{2}$ and $(2k-1)\ne n-(2k-1)$ (to ensure that the elements of $B$ are distinct). Tamizh Chelvam and Rani [10] obtained the value of the domination number of $Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. They identified a $\gamma$-set for $Cir(n,A)$ and having identified a $\gamma$-set, they found certain other $\gamma$-sets in $Cir(n,A)$ by using the inverse property of the underlying group. Among $Cir(n,A)$, they characterized all 2-excellent circulant graphs. In [11], they obtained $\gamma \gamma$-minimum, domatic number, independent domatic number, perfect domatic number and an $E$-set in these classes of circulant graphs. Further, they identified some circulant graphs which are having the properties of ${\gamma }_i$-excellent, just excellent and domatically full.

Theorem 4.1

[10, Theorem 2.1]

Let $n(\ge 3)$ and $k$ be positive integers such that $1\le k\le \frac{n-1}{2}$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-2,n-1$. Then $\gamma \left(G\right)=\lceil \frac{n}{A+1}\rceil$.

Remark 4.2

[10, Remark 2.5]

If $n(\ge 3)$ is an even integer and $A\ge \frac{n}{2}$, then $\gamma \left(Cir(n,A)\right)=\lceil \frac{n}{A+1}\rceil \le \lceil \frac{n}{\frac{n}{2}+1}\rceil \le \lceil \frac{2n}{n+2}\rceil \le 2$. If $n$ is odd and $A\ge \lfloor \frac{n}{2}\rfloor$, then $\gamma \left(Cir(n,A)\right)=\lceil \frac{n}{A+1}\rceil \le 2$.

Theorem 4.3

[10, Theorem 2.9]

Let $n(\ge 3)$ and $k$ be positive integers such that $1\le k\le \frac{n-1}{2}$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-2,n-1$. Then the graph $G=Cir(n,A)$ is excellent.

Theorem 4.4

[10, Theorem 2.10]

Let $n(\ge 3)$ and $k$ be positive integers such that $1\le k\le \frac{n-1}{2}$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-2,n-1$. Suppose $n=(2k+1)t+1$ for some positive integer $t$, then $G$ is $2$-excellent.

Lemma 4.5

[10, Lemma 2.7]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $\ell =\lceil \frac{n}{A+1}\rceil$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. If $n=(2k+1)(\ell -1)+h$, for some $h$ with $1\le h\le 2k$, then $D=0,h,h+(2k+1),h+2(2k+1),\dots ,h+(\ell -2)(2k+1)$ is a $\gamma$-set for $G$.

Theorem 4.6

[13, Theorem 2.5]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $\ell =\lceil \frac{n}{2k+1}\rceil$. Let $A=1,2,\dots ,k,n-k,\dots ,n-1$ and $n=(\ell -1)(2k+1)+j$ with $1\le j\le 2k$. Then $G=Cir(n,A)$ is $2$-excellent if and only if $j=1$.

Lemma 4.7

[16, Lemma 3.2.12]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then $D+h$ is a $\gamma$-set for any positive integer $h$ with $1\le h\le n-1$, whenever $D$ is a $\gamma$-set of $G$.

Lemma 4.8

[16, Lemma 3.2.13]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Suppose $n=(2k+1)t+h$ for some positive integers $t$ and $h$ with $1\le h\le 2k$ and $\ell =\lceil \frac{n}{A+1}\rceil$. Then $D=0,c+h,c+h+(2k+1),\dots ,c+h+(\ell -2)(2k+1)$ is a $\gamma$-set for $G$, where $1\le c\le 2k-h+1$.

Lemma 4.9

[16, Lemma 3.2.14]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. If $2k+1$ divides $n$, then $G$ is just excellent.

Lemma 4.10

[16, Lemma 3.2.15]

Let $n(\ge 3)$ be an even integer and $k$ be such that $1\le k\le \frac{n-1}{2}$. Suppose $D$ is a $\gamma$-set for $G_1=Cir(n,A_1)$, where $A_1=1,\dots ,k,n-k,\dots ,n-1$. Then $D$ is a dominating set for $G_2=Cir(n,A_2)$, where $A_2=1,\dots ,k,n-k,\dots ,n-1,\frac{n}{2}$.

The results given below identify independent and perfect domination numbers of $Cir(n,A)$.

Theorem 4.11

[11, Theorem 2.1]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $2k+1$ divides $n$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then $i\left(G\right)={\gamma }_p\left(G\right)=\frac{n}{2k+1}$.

The above theorem gives a tool to identify an E- set in $Cir(n,A)$ and the same provided by the corollary given below.

Corollary 4.12

[11, Corollary 2.2]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $2k+1$ divides $n$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$ and $D=0,(2k+1),2(2k+1),\dots ,(\lceil \frac{n}{2k+1}\rceil -1)(2k+1)$. Then for each $h$ with $1\le h\le 2k$, we have $D+h$ is both an independent and perfect dominating set of $G$.

Corollary 4.13

[11, Corollary 2.3]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $2k+1$ divides $n$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then $d_i\left(G\right)=d_p\left(G\right)=2k+1$.

Remark 4.14

[11, Remark 2.4]

For any vertex $v$ of $G=Cir(n,A)$, $N\left[v\right]=A+1$. In view of Lemma 4.5 and Theorem 4.11, $G$ has an efficient dominating set only when $2k+1$ divides $n.$

Corollary 4.15

[16, Corollary 3.4.6]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $2k+1$ divides $n$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then $G$ is domatically full.

Theorem 4.16

[11, Theorem 2.5]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $2k+1$ does not divide $n$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then $i\left(G\right)=\lceil \frac{n}{2k+1}\rceil .$

Theorem 4.17

[11, Theorem 2.8]

Let $n(\ge 3)$ and $k$ be positive integers such that $1\le k\le \frac{n-1}{2}.$ Then $ii\left(G\right)=\gamma i\left(G\right)=\gamma \gamma \left(G\right)=2\lceil \frac{n}{2k+1}\rceil$, where $G=Cir(n,A)$ and $A=1,2,\dots ,k,n-k,\dots ,n-1$.

Lemma 4.18

[16, Lemma 3.4.12]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then $G$ is $\gamma \gamma -$minimum.

I. Rani [16] obtained the values of domination and independent domination numbers for the class of circulant graphs $Cir(n,B)$, where $B=1,3,\dots ,2k-1,n-(2k-1),\dots ,n-3,n-1$ with $1\le k\le \frac{n-1}{2}$ and $(2k-1)\ne n-(2k-1)$.

Theorem 4.19

[16, Theorem 3.3.1]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $(2k-1)\ne n-(2k-1)$. Let $G=Cir(n,B)$, where $B=1,3,\dots ,2k-1,n-(2k-1),\dots ,n-3,n-1$. If $2k+1$ divides $n$, then $\gamma \left(G\right)=\frac{n}{2k+1}$.

Theorem 4.20

[16, Theorem 3.4.13]

Let $n(\ge 3)$ and $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $(2k-1)\ne n-(2k-1)$. Let $G=Cir(n,B)$, where $B=1,3,\dots ,2k-1,n-(2k-1),\dots ,n-3,n-1$. If $2k+1$ divides $n$, then $i\left(G\right)={\gamma }_p\left(G\right)=\frac{n}{2k+1}$.

Note that the set $D$ identified in Theorem 4.20 is an $E$-set in $Cir(n,B)$.

5 Connected domination in circulants

In this section, we present results concerning the total, connected and restrained domination parameters for $Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$.

Theorem 5.1

[12, Theorem 2.1]

Suppose $n(\ge 3)$ and $k$ are integers with $1\le k\le \frac{n-1}{2}$. Assume that $n=({\ell }_t-1)(3k+1)+h$ for some $h$ with $1\le h\le k$ and ${\ell }_t=\lceil \frac{n}{3k+1}\rceil$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then ${\gamma }_t\left(G\right)=2\lceil \frac{n}{3k+1}\rceil -1$.

Theorem 5.2

[12, Theorem 2.2]

Let $n(\ge 3)$, $k$ be integers such that $1\le k\le \frac{n-1}{2}$ and $3k+1$ divides $n$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then ${\gamma }_t\left(G\right)=\frac{2n}{3k+1}$.

Theorem 5.3

[12, Theorem 2.3]

Suppose $n(\ge 3)$ and $k$ are integers with $1\le k\le \frac{n-1}{2}$. Assume that $n=({\ell }_t-1)(3k+1)+h$ for some $h$ with $k+1\le h\le 3k$ and ${\ell }_t=\lceil \frac{n}{3k+1}\rceil$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then ${\gamma }_t\left(G\right)=2\lceil \frac{n}{3k+1}\rceil$.

Theorem 5.4

[12, Theorem 2.4]

Let $n(\ge 3)$ be an even integer and $k$ be an integer such that $1\le k\le \frac{n-2}{2}$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1,\frac{n}{2}$. If $4k+2$ does not divide $n$, then $2\lceil \frac{n}{4k+2}\rceil -1\le {\gamma }_t\left(G\right)\le 2\lceil \frac{n}{4k+2}\rceil$.

Lemma 5.5

[12, Lemma 2.6]

Suppose $n(\ge 3)$ and $k$ are integers with $1\le k\le \frac{n-1}{2}$. Let $A_1=1,n-1$, $A_2=1,2,\dots ,k,n-k,\dots ,n-1$. Then any ${\gamma }_t$-set of $G_1=Cir(n,A_1)$, is a total dominating set of $G_2=Cir(n,A_2)$.

We see the connected domination number of $Cir(n,A)$ in the following theorem.

Theorem 5.6

[12, Theorem 3.1]

Suppose $n(\ge 3)$ and $k$ are integers with $1\le k\le \frac{n-1}{2}$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then ${\gamma }_c\left(G\right)=\lceil \frac{n-(2k+1)}{k}\rceil +1$.

Lemma 5.7

[12, Lemma 3.2]

Let $n(\ge 4)$ be an even integer and $G=Cir(n,A)$, where $A=1,n-1,\frac{n}{2}$. Then ${\gamma }_c\left(G\right)\le \frac{n}{2}-1$.

Theorem 5.8

[12, Theorem 3.3]

Let $n(\ge 4)$ be an even integer and $k$ be an integer such that $1\le k\le \frac{n-1}{2}$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1,\frac{n}{2}$ . Then ${\gamma }_c\left(G\right)\le 2\lceil \frac{n-2(2k+1)}{2k}\rceil +2$.

Lemma 5.9

[12, Lemma 3.5]

Let $n(\ge 4)$ be an even integer and $k$ be an integer such that $k=\lceil \frac{n-2}{4}\rceil$. Let $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1,\frac{n}{2}$. Then $T=0,\frac{n}{2}$ is both ${\gamma }_t$-set and ${\gamma }_c$-set of $G$.

We have the restrained domination number of $Cir(n,A)$ in the following theorem.

Theorem 5.10

[16, Theorem 4.4.1]

Suppose $n,k$ are integers such that $2\le k\le \frac{n-1}{2}$ and $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then ${\gamma }_r\left(G\right)=\lceil \frac{n}{2k+1}\rceil$.

Theorem 5.11

[16, Theorem 4.4.2]

Let $n(\ge 3)$ be an integer and $G=Cir(n,A)$, where $A=1,n-1$. Suppose $n=3t$ or $3t+1$ for some positive integer $t$. Then ${\gamma }_r\left(G\right)=\lceil \frac{n}{3}\rceil$.

Theorem 5.12

[16, Theorem 4.4.3]

Let $n(\ge 3)$ be an integer and $G=Cir(n,A)$, where $A=1,n-1$. Suppose $n=3t+2$ for some positive integer $t$. Then ${\gamma }_r\left(G\right)=\lceil \frac{n}{3}\rceil +1$.

Theorem 5.13

[16, Theorem 4.4.4]

Suppose $n(\ge 3)$ and $k$ are integers such that $1\le k\le \frac{n-1}{2}$ and $G=Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$. Then $1\le {\gamma }_r\left(G\right)\le \lceil \frac{n}{3}\rceil +1$.

Theorem 5.14

[16, Theorem 4.4.5]

Let $n(\ge 3)$ be an even integer and $k$ be an integer such that $1\le k\le \frac{n-1}{2}$. Let $G_1=Cir(n,A_1)$, where $A_1=1,2,\dots ,k,n-k,\dots ,n-1$ and $G_2=Cir(n,A_2)$, where $A_2=1,2,\dots ,k,n-k,\dots ,n-1,\frac{n}{2}$. Any ${\gamma }_r$-set of $G_1$ is a restrained dominating set of $G_2$.

6 Domination in another class of circulants

In the previous section, we have presented results on domination parameters for the circulant graphs $Cir(n,A)$, where $A=1,2,\dots ,k,n-k,\dots ,n-1$ with $1\le k\le \frac{n}{2}$. This section focuses on the domination number, total domination number and connected domination number for circulant graphs with respect to the generating sets $m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$ when $n$ is odd and $m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$ when $n$ is even. Here, $m$ and $k$ are integers such that $m=\lfloor \frac{n-1}{2}\rfloor$ and $1\le k\le m$.

Lemma 6.1

[17, Lemma 3.2.1]

Let $n(\ge 3)$ be an odd integer, $m=\frac{n-1}{2}$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$. If $\lceil \frac{n}{2k+1}\rceil$ is odd, then $\gamma \left(G\right)=\lceil \frac{n}{2k+1}\rceil$.

Corollary 6.2

[17, Corollary 3.2.2]

Let $n(\ge 3)$ be an odd integer, $m=\frac{n-1}{2}$ and $k$ be an integer such that $2k+1$ divides $n$ with $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$. Then $G$ has an efficient dominating set.

When $n$ and $\lceil \frac{n}{2k+1}\rceil$ are odd, it is proved that $\gamma \left(G\right)=\lceil \frac{n}{2k+1}\rceil$. But it is not true in general when $\lceil \frac{n}{2k+1}\rceil$ is even. The next lemma gives the value of the domination number when $\lceil \frac{n}{2k+1}\rceil$ is even.

Lemma 6.3

[17, Lemma 3.2.4]

Let $n(\ge 3)$ be an odd integer, $m=\frac{n-1}{2}$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$.

(a)	If $\ell =\lceil \frac{n}{2k+1}\rceil$ is even and $m-k=(\frac{\ell }{2}-1)(2k+1)+1$, then $\gamma \left(G\right)=\lceil \frac{n}{2k+1}\rceil$.

(b)	If $\ell =\lceil \frac{n}{2k+1}\rceil$ is even and $m-k=(\frac{\ell }{2}-1)(2k+1)+j$, for some integer $j$ with $2\le j\le k$, then $\gamma \left(G\right)\le \lceil \frac{n}{2k+1}\rceil +1$.

Using Lemmas 6.1 and 6.3, the following theorem is proved which gives lower and upper bounds for domination number.

Theorem 6.4

[17, Theorem 3.2.5]

Let $n(\ge 3)$ be an odd integer, $m=\frac{n-1}{2}$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$. Then $\lceil \frac{n}{2k+1}\rceil \le \gamma \left(G\right)\le \lceil \frac{n}{2k+1}\rceil +1$.

Lemma 6.5

[17, Lemma 3.2.6]

Let $n(\ge 3)$ be an even integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$. If $\lceil \frac{n}{2k+2}\rceil$ is odd, then $\gamma \left(G\right)=\lceil \frac{n}{2k+2}\rceil$.

Corollary 6.6

[17, Corollary 3.2.7]

Let $n(\ge 3)$ be an even integer, $m=\lfloor \frac{n-1}{2}\rfloor$ and $k$ be an integer such that $2k+2$ divides $n$ with $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$. If $\frac{n}{2k+2}$ is odd, then $G$ has an efficient dominating set.

Lemma 6.7

[17, Lemma 3.2.8]

Let $n(\ge 3)$ be an even integer, $m=\lfloor \frac{n-1}{2}\rfloor$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$.

(a)	If $\ell =\lceil \frac{n}{2k+2}\rceil$ is even and $m-k=(\frac{\ell }{2}-1)(2k+2)+1$, then $\gamma \left(G\right)=\lceil \frac{n}{2k+2}\rceil$.

(b)	If $\ell =\lceil \frac{n}{2k+2}\rceil$ is even and $m-k=(\frac{\ell }{2}-1)(2k+2)+j$, for some integer $j$ with $2\le j\le k+1$, then $\gamma \left(G\right)\le \lceil \frac{n}{2k+2}\rceil +1$.

Using Lemmas 6.5 and 6.7, the following result is arrived.

Theorem 6.8

[17, Theorem 3.2.9]

Let $n(\ge 3)$ be an even integer, $m=\lfloor \frac{n-1}{2}\rfloor$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$. Then $\lceil \frac{n}{2k+2}\rceil \le \gamma \left(G\right)\le \lceil \frac{n}{2k+2}\rceil +1$.

7 Total and efficient open domination

In this section, we list the results on the total domination number and a corresponding minimum total dominating set for the class of circulant graphs $Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$ when $n$ is odd and $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$ when $n$ is even. Note that certain circulant graphs in this class admit efficient open dominating sets.

Lemma 7.1

[18, Lemma 2.1]

Let $n(\ge 3)$ be an odd integer, $m=\frac{n-1}{2}$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$. Then ${\gamma }_t\left(G\right)=\lceil \frac{n}{2k}\rceil$.

Corollary 7.2

[17, Corollary 3.3.2]

Let $n(\ge 3)$ be an odd integer, $m=\frac{n-1}{2}$ and $k$ be an integer such that $2k$ divides $n$ with $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$. Then $G$ has an efficient open dominating set.

Lemma 7.3

[18, Lemma 2.2]

Let $n(\ge 3)$ be an even integer, $m=\lfloor \frac{n-1}{2}\rfloor$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$. Then ${\gamma }_t\left(G\right)=\lceil \frac{n}{2k+1}\rceil$.

Corollary 7.4

[17, Corollary 3.3.5]

Let $n(\ge 3)$ be an even integer, $m=\lfloor \frac{n-1}{2}\rfloor$ and $k$ be an integer such that $2k+1$ divides $n$ with $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$. Then $G$ has an efficient open dominating set.

In Lemma 7.3, each interval (except $I_{\ell }$) contains exactly $2k+1$ vertices and $1\le I_{\ell }\le 2k+1.$ From this, one can find that the vertices $1,2,\dots ,(2k+1)-j$ are dominated by both $x(=m+k+2)$ and $x+(\ell -1)(2k+1)$ and they are the only vertices dominated by two vertices in the ${\gamma }_t$-set $D_t$ specified in Lemma 7.3.

Since the vertices of $V\left(G\right)$ are group elements, $D_t+y$ is a ${\gamma }_t$-set for all $y\in V\left(G\right)$. This implies that $G$ is total excellent. In particular, $D_t^{\prime }=D_t+(n-x)=0,2k,2\left(2k\right),\dots ,(\ell -1)2k$ when $n$ is odd and $D_t^{″}=D_t+(n-x)=0,(2k+1),2(2k+1),\dots ,(\ell -1)(2k+1)$ when $n$ is even, are also ${\gamma }_t$-sets of $G=Cir(n,A)$ with respective to the generating sets $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$ and $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$, respectively. Further, certain 2-total excellent circulant graphs are identified in the following results.

Lemma 7.5

[18, Lemma 3.1]

Let $n(\ge 3)$ be an odd integer, $m=\frac{n-1}{2}$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$. If $n=t\left(2k\right)+1$ for some integer $t>0$, then $G$ is 2-total excellent.

Theorem 7.6

[18, Theorem 3.2]

Let $n(\ge 3)$ be an odd integer, $m=\frac{n-1}{2}$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,n-m,n-(m-1),\dots ,n-(m-(k-1))$. If $n=t\left(2k\right)+j$ for some integers $t(>0)$ and $j$ with $1\le j\le 2k$, then $G$ is 2-total excellent if and only if $j=1$.

Lemma 7.7

[18, Lemma 3.3]

Let $n(\ge 3)$ be an even integer, $m=\lfloor \frac{n-1}{2}\rfloor$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$. If $n=t(2k+1)+1$ for some integer $t(>0)$, then $G$ is 2-total excellent.

Theorem 7.8

[18, Theorem 3.4])

Let $n(\ge 3)$ be an even integer, $m=\lfloor \frac{n-1}{2}\rfloor$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=m-(k-1),\dots ,m-1,m,\frac{n}{2},n-m,n-(m-1),\dots ,n-(m-(k-1))$. If $n=t(2k+1)+j$ for some integers $t(>0)$ and $j$ with $1\le j\le 2k+1$, then $G$ is 2-total excellent if and only if $j=1$.

8 Domination in general circulants

In this section, we concentrate on upper bounds for the domination number, total domination number and connected domination number of an arbitrary circulant graph. Further, it is proved that the upper bound is reachable in certain cases. In those cases, the domatic number and independent domatic number are also obtained. Throughout this section, the generating set $A$ of ${\mathbb{Z}}_n$ is taken as $A=a_1,a_2,\dots ,a_k,n-a_k,n-a_{k-1},\dots ,n-a_1$, where $1\le a_1<a_2<\cdots <a_k\le m$, $d_1=a_1$, $d_i=a_i-a_{i-1}$ for $2\le i\le k$ and $d={}_{1\le i\le k}^{max}{d}_i$.

Lemma 8.1

[14, Lemma 2.1]

Let $n(\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=a_1,a_2,\dots ,a_k,n-a_k,n-a_{k-1},\dots ,n-a_1$. If $d_1=a_1$, $d_i=a_i-a_{i-1}$ for $2\le i\le k$ and $d={}_{1\le i\le k}^{max}{d}_i$, then $\gamma \left(G\right)\le d\lceil \frac{n}{d+2a_k}\rceil$.

By taking $d_1=d_2=\cdots =d_k=d$, the following corollary is proved.

Corollary 8.2

[17, Corollary 4.1.2]

Let $n(\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k,d$ be integers such that $1\le kd\le m$. Let $G=Cir(n,A)$, where $A=d,2d,\dots ,kd,n-kd,n-(k-1)d,\dots ,n-d$. Then $\gamma \left(G\right)\le d\lceil \frac{n}{d(1+2k)}\rceil$.

Theorem 8.3

[14, Theorem 2.3])

Let $n(\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k,d$ be integers such that $1\le kd\le m$. Let $G=Cir(n,A)$, where $A=d,2d,\dots ,kd,n-kd,n-(k-1)d,\dots ,n-d$. If $d(1+2k)$ divides $n$, then $\gamma \left(G\right)=\frac{n}{1+2k}$. In this case, $G$ has an efficient dominating set.

Lemma 8.4

[14, Lemma 2.4]

Let $n(\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k,d$ be integers such that $1\le kd\le m$. Let $G=Cir(n,A)$, where $A=d,2d,\dots ,kd,n-kd,n-(k-1)d,\dots ,n-d$. Suppose $d(1+2k)$ divides $n$, then $d\left(G\right)=d_i\left(G\right)=d_p\left(G\right)=2k+1$.

Lemma 8.5

[14, Lemma 2.2]

Let $n(\ge 3)$ be an integer, $k,d$ be integers such that $1\le kd\le m=\lfloor \frac{n-1}{2}\rfloor$and $\ell =\lceil \frac{n}{d+2kd}\rceil$. Let $G=Cir(n,A)$, where $A=d,2d,\dots ,kd,n-kd,n-(k-1)d,\dots ,n-d$. Suppose $n=\ell (d+2kd)+j$ for some integer $j$ with $1\le j\le d(1+2k)$. Then

(a)	$\gamma \left(G\right)\le d(\ell -1)+j$ if $1\le j\le d-1$.

(b)	$\gamma \left(G\right)\le d\ell$ otherwise.

The results given below identify an upper bound for the total domination number and the connected domination number for a general circulant graph.

Theorem 8.6

[14, Theorem 3.1]

Let $n(\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$ and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=a_1,a_2,\dots ,a_k,n-a_k,n-a_{k-1},\dots ,n-a_1$. If $d_1=a_1$, $d_i=a_i-a_{i-1}$ for $2\le i\le k$ and $d={}_{1\le i\le k}^{max}{d}_i$, then ${\gamma }_t\left(G\right)\le 2d\lceil \frac{n}{d+3a_k}\rceil$.

Corollary 8.7

[17, Corollary 4.2.2]

Let $n(\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k,d$ be integers such that $1\le kd\le m$. Let $G=Cir(n,A)$, where $A=d,2d,\dots ,kd,n-kd,n-(k-1)d,\dots ,n-d$. Then ${\gamma }_t\left(G\right)\le 2d\lceil \frac{n}{d(1+3k)}\rceil$.

In the above corollary, if $d=1$, then we have ${\gamma }_t\left(G\right)\le 2\lceil \frac{n}{1+3k}\rceil$. Since $\Delta \left(G\right)=2k$ and from the nature of elements in $A$, any two adjacent vertices can dominate at most $3k+1$ different vertices of $G$. Thus, ${\gamma }_t\left(G\right)\ge 2\lceil \frac{n}{1+3k}\rceil$ and so ${\gamma }_t\left(G\right)=2\lceil \frac{n}{1+3k}\rceil$.

Lemma 8.8

[14, Lemma 3.2]

Let $(n\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k,d$ be integers such that $1\le kd\le m$. Let $G=Cir(n,A)$, where $A=d,2d,\dots ,kd,n-kd,n-(k-1)d,\dots ,n-d$. Suppose $n=\ell (d+3kd)+j$ for some $1\le j\le d+3kd$, where $\ell =\lceil \frac{n}{d+3kd}\rceil$, then

(a)	${\gamma }_t\left(G\right)\le 2d(\ell -1)+j$, if $1\le j\le d-1$;

(b)	${\gamma }_t\left(G\right)\le 2d\ell$, otherwise.

Lemma 8.9

[14, Lemma 3.3]

Let $(n\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k,d$ be integers such that $1\le kd\le m$. Let $G=Cir(n,A)$, where $A=d,2d,\dots ,kd,n-kd,n-(k-1)d,\dots ,n-d$. Suppose $d(1+3k)$ divides $n$, then ${\gamma }_t\left(G\right)=\frac{2n}{1+3k}$.

Lemma 8.10

[14, Lemma 3.5]

Let $n(\ge 3)$ be an integer, $m=\lfloor \frac{n-1}{2}\rfloor$and $k$ be an integer such that $1\le k\le m$. Let $G=Cir(n,A)$, where $A=1,a_2,\dots ,a_k,n-a_k,n-a_{k-1},\dots ,n-a_2,n-1$. If $d_1=1$, $d_i=a_i-a_{i-1}$ for $2\le i\le k$ and $d={}_{1\le i\le k}^{max}{d}_i$, then ${\gamma }_c\left(G\right)\le d(1+\lceil \frac{n-(d+2a_k)}{a_k}\rceil )$.

9 Efficient dominating sets in circulant graphs of large degree

In this section, results about wreath products of circulant graphs are presented and they identify infinitely many circulant graphs with efficient dominating sets whose elements need not be equally spaced in ${\mathbb{Z}}_n$. Kumar and MacGillivray [19] proved that if a circulant graph of large degree has an efficient dominating set, then either its elements are equally spaced or the graph is the wreath product of a smaller circulant graph with an efficient dominating set and a complete graph.

The following statement about wreath products of circulant graphs was proved by Broere and Hattingh [20]. For $d\in {\mathbb{Z}}_n$, the symbol $〈d〉$ denotes the subgroup of ${\mathbb{Z}}_n$ generated by $d$. The wreath product of two graphs $G$ and $H$ is denoted by $G\sim H$.

Theorem 9.1

[20, Proposition 27]

If $G=Cir(n,S)$ and $H=Cir(m,T)$ are circulant graphs, then $G\sim H$ is isomorphic to $F=Cir(mn,nT\cup (\bigcup _{s\in S}n{\mathbb{Z}}_m+s))$. Further, the subgraph of $F$ induced by choosing one representative from each coset of $〈n〉$ is isomorphic to $G$, and the subgraph of $F$ induced by any coset of $〈n〉$is isomorphic to $H$.

Proposition 9.2

[19, Proposition 3.2]

Let $G$ be a graph without isolated vertices and $H$ be a graph with at least one vertex. Then $G\sim H$ has an efficient dominating set if and only if $G$ has an efficient dominating set and $\gamma \left(H\right)=1$.

Theorem 9.3

[19, Theorem 3.3]

The graph $G=Cir(mn,S)$ is isomorphic to the wreath product of a circulant graph on $n$ vertices and $K_m$ if and only if $S\cup 0$is a union of cosets of $〈n〉$.

Corollary 9.4

[19, Corollary 3.4]

Let $F=Cir(mn,T)$ and suppose $T\cup 0$is a union of cosets of $〈n〉$. Let $S$ be any set of representatives of the cosets $〈n〉+t$, $t\in T-〈n〉$. Then $F$ has an efficient dominating set if and only if $G=Cir(n,T)$ has an efficient dominating set.

The largest possible values of the degree of an $n$-vertex circulant graph, which is not complete and which might have an efficient dominating set, are $\frac{n}{2}-1$ and $\frac{n}{3}-1$. These graphs have domination number two and three, respectively. The above ideas are used to completely describe their efficient dominating sets.

We call a circulant graph reducible if it is a wreath product of a smaller circulant graph and a complete graph with at least two vertices; otherwise, we call it irreducible. By Theorem 9.3, $Cir(n,S)$ is reducible if and only if $S\cup 0$ is a union of cosets of $〈d〉$ for some divisor $d$ of $n$ with $d>1$.

Proposition 9.5

[19, Proposition 4.1]

Suppose that the reducible circulant graph $Cir(n,S)$ has an efficient dominating set. If $d$ is the smallest positive integer such that $S\cup 0$ is a union of cosets of $〈d〉$, then $d$ divides $n$, $m=n∕d$ divides $S+1$ and $Cir(n,S)$ is the wreath product of an irreducible circulant graph and $K_m$.

Theorem 9.6

[19, Theorem 4.2]

Suppose $S=k-1$ and $G=Cir(2k,S)$ has an efficient dominating set, $D$. Then either $S\cup 0$ is a union of cosets of a nontrivial proper subgroup of ${\mathbb{Z}}_{2k}$, or $D$ is a coset of $〈k〉$.

Corollary 9.7

[19, Corollary 4.3]

Suppose that $G=Cir(2k,S)$, where $S=k-1$, has an efficient dominating set.

(a)	If $G$ is irreducible, then every efficient dominating set is equally spaced. In particular, $0,k$ is an efficient dominating set.

(b)	If $G$ is reducible, then there exist integers $n$ and $m$ such that $m\ge 2$ and $G$ is the wreath product of the irreducible circulant graph $Cir(2n,T)$, where $T=n-1$, and $K_m$. Further, $Cir(2n,T)$ has an efficient dominating set.

Theorem 9.8

[19, Theorem 4.4]

Suppose $S=k-1$ and $G=Cir(3k,S)$ has an efficient dominating set, $D$. Then either $S\cup 0$ is a union of cosets of a nontrivial proper subgroup of ${\mathbb{Z}}_{3k}$, or $D$ is a coset of $〈k〉$.

Corollary 9.9

[19, Corollary 4.5]

Suppose that $G=Cir(3k,S)$, where $S=k-1$, has an efficient dominating set.

(a)	If $G$ is irreducible, then every efficient dominating set is equally spaced. In particular, $0,k,2k$ is an efficient dominating set.

(b)	If $G$ is reducible, then there exist integers $n$ and $m$ such that $m\ge 2$ and $G$ is the wreath product of the irreducible circulant graph $Cir(3n,T)$, where $T=n-1$, and $K_m$. Further, $Cir(3n,T)$ has an efficient dominating set.

10 Subgroups as efficient dominating sets

As circulant graphs are constructed from the group ${\mathbb{Z}}_n$, there is a relationship between the substructures of the group ${\mathbb{Z}}_n$ and that of the corresponding graph $Cir(n,A)$. Trivially, every efficient dominating set of $Cir(n,A)$ is a subset of the group ${\mathbb{Z}}_n$ and so there is a possibility for an efficient dominating set of $Cir(n,A)$ to be a subgroup of ${\mathbb{Z}}_n$. With this in mind, a necessary and sufficient condition was obtained by Tamizh Chelvam and Mutharasu [15] for a subgroup of ${\mathbb{Z}}_n$ to be an efficient dominating set of $Cir(n,A)$ for some suitable generating set $A$ of ${\mathbb{Z}}_n$.

Lemma 10.1

[15, Lemma 3.1]

Let $H$ be a proper subgroup of ${\mathbb{Z}}_n$ such that $n=H(2k+1)$ for some integer $k\ge 1$. Then there exists a generating set $A$ of ${\mathbb{Z}}_n$ such that $H$ is an efficient dominating set for the circulant graph $G=Cir(n,A)$.

Corollary 10.2

[15, Corollary 3.2]

Let $H$ be a proper subgroup of ${\mathbb{Z}}_n$ such that $n=H(2k+1)$ for some integer $k\ge 1$. Then there exists a generating set $A$ of ${\mathbb{Z}}_n$ such that for every $x\in \Gamma$, the co-set $H+x$ is an efficient dominating set for the circulant graph $G=Cir(n,A)$.

Lemma 10.3

[15, Lemma 3.3]

Let $H$ be a proper subgroup of ${\mathbb{Z}}_n$ such that $H$ is odd and $n=H(2k+2)$ for some integer $k\ge 1$. Then there exists a generating set $A$ of ${\mathbb{Z}}_n$ such that $H$ is an efficient dominating set for the circulant graph $G=Cir(n,A)$.

By the above lemma and the property of vertex transitivity on circulant graphs, the following corollary was obtained.

Corollary 10.4

[15, Corollary 3.4]

Let $H$ be a proper subgroup of ${\mathbb{Z}}_n$ such that $H$ is odd and $n=H(2k+2)$ for some integer $k\ge 1$. Then there exists a generating set $A$ of ${\mathbb{Z}}_n$ such that for every $x\in \Gamma$, the co-set $H+x$ is an efficient dominating set for the circulant graph $G=Cir(n,A)$.

Theorem 10.5

[15, Theorem 3.6]

Let $H$ be a proper subgroup of ${\mathbb{Z}}_n$. Then $H$(as well as $H+x$ for any $x\in {\mathbb{Z}}_n$) is an efficient dominating set in $G=Cir(n,A)$ for some suitable generating set $A$ of ${\mathbb{Z}}_n$ if and only if either of the following is true.

(a)	$n=H(2k+1)$ for some integer $k\ge 1$;

(b)	$n=H(2k+2)$ for some integer $k\ge 1$ and $H$ is odd.

Notes

Peer review under responsibility of Kalasalingam University.