betaFeedback

WorksMathematics

Notes on efficient dominating sets and efficient open dominating sets in circulant graphs

Abstract

Let DD be a proper subset of Zn\mathbb{Z}_n such that ∣D∣|D| divides nn and is relatively prime to n∣D∣\frac{n}{|D|}. We first establish a necessary and sufficient condition for DD to be an efficient dominating set of some circulant graph \Cay(\mathbb{Z}_n,S). Moreover, for an inverse-closed subset SS of Zn∖{0}\mathbb{Z}_n\setminus\{0\} such that ∣S∣+1|S|+1 divides nn and is relatively prime to n∣S∣+1\frac{n}{|S|+1}, we give a necessary and sufficient condition for the existence of efficient dominating sets in \Cay(\mathbb{Z}_n,S). We also obtain some results about the set of all efficient dominating sets in any circulant graph. Similar results for efficient open dominating sets are also obtained. These results extend some theorems in [Discrete Math. 340 (2017) 1503–1507], [Discrete Math. 340 (2017) 1522–1527], and [Des. Codes Cryptogr. 94 (2026), 87].

AMS Classifications: 05C25, 05C69

Introduction

Let GG be a finite group with identity element ee and SS an inverse-closed subset of GG not containing ee. The Cayley graph on GG with respect to the connection set SS is defined as the graph with vertex set GG and edge set {{g,sg}:g∈G, s∈S}\{\{g,sg\}: g\in G,\ s\in S\} and denoted by Cay⁡(G,S)\operatorname{Cay}(G,S). A Cayley

E-mail addresses: [email protected] (Deng), [email protected] (Ma) graph on finite cyclic group Zn:={0,1,⋯ ,n−1}\mathbb{Z}_n := \{0,1,\cdots,n-1\} with addition modulo nn is called a circulant graph.

A subset DD of vertices in a graph Γ\Gamma is called an efficient dominating set (also called a perfect code) if DD is an independent set and each vertex not in DD is adjacent to exactly one vertex in DD. By the definitions of a circulant graph and an efficient dominating set, it is easy to see that if Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set DD, then n=(∣S∣+1)∣D∣n=(|S|+1)|D|. A subset DD of vertices in a graph Γ\Gamma is called an efficient open dominating set (also called a total perfect code) if each vertex in Γ\Gamma is adjacent to exactly one vertex in DD. Similarly, one can easily see that if Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient open dominating set DD, then n=∣S∣∣D∣n=|S||D|, and DD induces a matching in Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S), which implies that ∣D∣|D| is even.

The existence of efficient dominating sets in some families of graphs was first studied by Biggs [1] and Kratochvíl [9]. It was proved in [11] that a Cayley graph on an abelian group admits an efficient dominating set if and only if it is a covering graph of a complete graph. In [3], a method for constructing E-chains of Cayley graphs was given and was used to construct infinite families of E-chains of Cayley graphs on symmetric groups, where an EE-chain is a countable family of nested graphs each containing an efficient dominating set. In [14], Terada showed that there exists no efficient dominating set in any Cayley graph on special linear group SL⁡(2,2f)\operatorname{SL}(2,2^{f}) (f>1f>1) with respect to a conjugation-closed connection set.

During the past two decades, efficient dominating sets in circulant graphs have attracted considerable attention. For example, Kumar and MacGillivray [10] characterized the efficient dominating sets in circulant graphs with domination number two and three, and Deng [4] further characterized the existence and construction of efficient dominating sets with domination number prime. In [12], Obradović, Peters and Ružić gave necessary and sufficient conditions for the existence of efficient dominating sets in connected circulant graphs of degree 3 and 4. Applying the tool of cyclotomic polynomials, Feng et al. [7] generalized the results in [12] by considering the case of degree pl−1p^{l}-1 (pp prime and ll positive integer). Almost at the same time, using the subset direct sum method, Deng et al. [5] independently gave necessary and sufficient conditions for the existence of efficient dominating sets in connected non-complete circulant graphs Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) of degree ∣S∣=p−1|S|=p-1, pq−1pq-1 and pm−1p^{m}-1 (p,qp,q primes and mm positive integer) or order n=pkqn=p^{k}q, p2q2p^{2}q^{2}, pqrpqr, p2qrp^{2}qr, pqrspqrs (p,q,r,sp,q,r,s distinct primes and kk positive integer) satisfying that ∣S∣+1|S|+1 divides nn and ∣S∣+1|S|+1 is relatively prime to n∣S∣+1\frac{n}{|S|+1}. Efficient open dominating sets have also received much attention in recent years. In [8], Corollary 3.5 (b), Huang et al. gave a necessary and sufficient condition for a subgroup to be an efficient open dominating set in circulant graphs. Feng et al. [7] gave a necessary and sufficient condition for the existence of efficient open dominating sets in connected circulant graphs Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) of degree ∣S∣=pl|S|=p^{l}. (pp prime and ll positive integer) satisfying that ∣S∣|S| divides nn and ∣S∣|S| is relatively prime to n∣S∣\frac{n}{|S|}.

In terms of the order of a cyclic group and the cardinality of an efficient dominating set (resp. an efficient open dominating set), Feng et al. [6] gave a necessary and sufficient condition for the existence of efficient dominating sets (resp. efficient open dominating sets) in circulant graphs. Wang et al. [16] studied efficient dominating sets in circulant graphs of degree pl−1p^l-1, where pp is a prime and l≥1l \ge1, which extended known results in [7] and provided insight on the general problem on the existence and structure of efficient dominating sets in circulant graphs. Recently, Cameron et al. [2] generalized some results in [7] to general abelian groups.

In this note, we generalize the results in [2], [5], and [7] by proving that the similar result holds for any circulant graph Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) of general degree ∣S∣|S| and general order nn satisfying that ∣S∣+1|S|+1 divides nn and ∣S∣+1|S|+1 is relatively prime to n∣S∣+1\frac{n}{|S|+1}. Furthermore, for any circulant graph which admits an efficient dominating set, the present paper gives some results about the set of all its efficient dominating sets. We further give a necessary and sufficient condition for a general subset to be an efficient dominating set in circulant graphs. Similar results for efficient open dominating sets are also obtained.

Preliminaries

Let GG be a finite abelian group with additive notation, and let M,NM,N be two subsets of GG. If every g∈Gg \in G has a unique representation in the form g=m+ng=m+n with m∈Mm \in M, n∈Nn \in N, then GG is called the direct sum of MM and NN. In this case, we write G=M⊕NG=M\oplus N. For two positive integers m,nm,n, we use (m,n)(m,n) to denote the greatest common divisor of mm and nn. If (m,n)=1(m,n)=1, then mm and nn are relatively prime.

Proposition 2.1 ([15 Proposition 2.1]) Let GG be a finite abelian group and let M,NM,N be subsets of GG. Then G=M⊕NG=M\oplus N is equivalent to the conjunction of any two of the following conditions:

(i) G=M+NG=M+N;

(ii) (M−M)∩(N−N)={0}(M-M)\cap(N-N)=\{0\};

(ii) ∣G∣=∣M∣∣N∣|G|=|M||N|.

If SS is a subset of a finite abelian group GG, then we write S0=S∪{0}S_0=S\cup\{0\}.

Lemma 2.2 ([4 Lemma 2.3]) A subset DD of finite abelian group GG is an efficient dominating set of Cay⁡(G,S)\operatorname{Cay}(G,S) if and only if G=S0⊕DG=S_0\oplus D.

For any subset MM of an abelian group GG, the set of all g∈Gg \in G satisfying g+M=Mg + M = M is a subgroup of GG, called the stability subgroup of MM, denoted by GMG_M. It is easy to see that MM is a union of cosets of GMG_M. Moreover, if 0∈M0 \in M, then GM⊆MG_M \subseteq M. A subset M⊆GM \subseteq G is called periodic if GM≠{0}G_M \ne\{0\}. Otherwise, a subset M⊆GM \subseteq G is called aperiodic if GM={0}G_M = \{0\}.

Lemma 2.3 ([4 Lemma 2.4]) Let SS and DD be two subsets of finite abelian group GG, and let A=GS0A = G_{S_0}. Then G=S0⊕DG = S_0 \oplus D if and only if G/A=S0/A⊕(D+A)/AG/A = S_0/A \oplus(D + A)/A and A∩(D−D)={0}A \cap(D - D) = \{0\}.

Lemma 2.4 ([13 Theorem 3.17]) Let GG be a finite abelian group, and let M,NM, N be subsets of GG. If G=M⊕NG = M \oplus N, then G=kM⊕NG = kM \oplus N for any integer kk relatively prime to ∣M∣|M|, where kM={km:m∈M}kM = \{km: m \in M\}.

The following result was first stated in [12 Remark 1] and also appears in [4].

Lemma 2.5 ([12 Remark 1]) Let n=∣S0∣dn = |S_0|d, where dd is an integer. Then Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n, S) admits an efficient dominating set DD which is a coset of some subgroup of Zn\mathbb{Z}_n if and only if s−s′≠0(mod∣S0∣)s - s' \ne0 \pmod{|S_0|} for any distinct s,s′∈S0s, s' \in S_0, where S0=S∪{0}S_0 = S \cup\{0\}.

By the definitions of a Cayley graph and an efficient open dominating set, similar to Lemma 2.2, one can easily obtain the following result.

Lemma 2.6 A subset DD of a finite abelian group GG is an efficient open dominating set of Cay⁡(G,S)\operatorname{Cay}(G,S) if and only if G=S⊕DG = S \oplus D.

Similar to Lemma 2.5, we have the following result.

Lemma 2.7 Let n=∣S∣dn = |S|d, where dd is an integer. Then Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient open dominating set DD which is a coset of some subgroup of Zn\mathbb{Z}_n if and only if s−s′≠0(mod∣S∣)s - s' \ne0 \pmod{|S|} for any distinct s,s′∈Ss, s' \in S.

Efficient dominating sets

Clearly, if Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set DD, then n=(∣S∣+1)∣D∣n = (|S| + 1)|D|. We first establish a necessary and sufficient condition for a proper subset DD of Zn\mathbb{Z}_n with ∣D∣∣n|D| \mid n and (∣D∣,n∣D∣)=1\left(|D|,\frac{n}{|D|}\right) = 1 to be an efficient dominating set of Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S).

Theorem 3.1 Let DD be a proper subset of Zn\mathbb{Z}_n such that ∣D∣|D| divides nn and is relatively prime to n∣D∣\frac{n}{|D|}. Then DD is an efficient dominating set of some circulant graph Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) if and only if d−d′≠0(mod∣D∣)d - d' \ne0 \pmod{|D|} for distinct d,d′∈Dd, d' \in D.

Proof. Suppose that d−d′≠0(mod∣D∣)d-d' \ne0 \pmod{|D|} for distinct d,d′∈Dd,d' \in D. Then

(∣D∣Zn−∣D∣Zn)∩(D−D)={0}.(|D|\mathbb{Z}_n-|D|\mathbb{Z}_n)\cap(D-D)=\{0\}.

Note that the cardinality of ∣D∣Zn|D|\mathbb{Z}_n is n∣D∣\frac{n}{|D|}. Therefore, by Proposition 2.1, Zn=∣D∣Zn⊕D\mathbb{Z}_n=|D|\mathbb{Z}_n\oplus D. Now let S=∣D∣Zn∖{0}S=|D|\mathbb{Z}_n\setminus\{0\}. Then SS is inverse-closed and Zn=S0⊕D\mathbb{Z}_n=S_0\oplus D, where S0=S∪{0}S_0=S\cup\{0\}. By Lemma 2.2, DD is an efficient dominating set in Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S), as desired.

Conversely, suppose that DD is an efficient dominating set in Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S). Then by Lemma 2.2, Zn=S0⊕D\mathbb{Z}_n=S_0\oplus D, where S0=S∪{0}S_0=S\cup\{0\}. Set ∣S0∣=k|S_0|=k. Then n=k∣D∣n=k|D| and kk is relatively prime to ∣D∣|D|. It follows from Lemma 2.4 that Zn=S0⊕kD\mathbb{Z}_n=S_0\oplus kD, which implies that ∣kD∣=∣D∣|kD|=|D|. Now we claim that d−d′≠0(mod∣D∣)d-d'\ne0\pmod{|D|} for any distinct d,d′∈Dd,d'\in D. Otherwise, if there exist some distinct d,d′∈Dd,d'\in D such that d−d′≡0(mod∣D∣)d-d'\equiv0\pmod{|D|}, then kd−kd′≡0(modk∣D∣)kd-kd'\equiv0\pmod{k|D|}, that is, kd−kd′≡0(modn)kd-kd'\equiv0\pmod n. Therefore, kdkd and kd′kd' are the same element in Zn\mathbb{Z}_n, and thus ∣kD∣<∣D∣|kD|<|D|, which is a contradiction. ■

If SS is an inverse-closed subset of Zn∖{0}\mathbb{Z}_n\setminus\{0\} such that (∣S∣+1)∣n(|S|+1)\mid n and (∣S∣+1,n∣S∣+1)=1\left(|S|+1,\frac{n}{|S|+1}\right)=1, then the following result gives a necessary and sufficient condition for which Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set.

Theorem 3.2 Let SS be an inverse-closed subset of Zn∖{0}\mathbb{Z}_n\setminus\{0\} such that ∣S∣+1|S|+1 divides nn and is relatively prime to n∣S∣+1\frac{n}{|S|+1}. Then Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set if and only if s−s′≠0(mod∣S0∣)s-s'\ne0\pmod{|S_0|} for distinct s,s′∈S0s,s'\in S_0.

Proof. If s−s′≠0(mod∣S0∣)s-s'\ne0\pmod{|S_0|} for distinct s,s′∈S0s,s'\in S_0, then by Lemma 2.5, Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set.

For the converse, suppose that Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set DD. Then by Lemma 2.2, Zn=S0⊕D\mathbb{Z}_n=S_0\oplus D. Set ∣D∣=k|D|=k. Then n=∣S0∣kn=|S_0|k and kk is relatively prime to ∣S0∣|S_0|. It follows from Lemma 2.4 that Zn=kS0⊕D\mathbb{Z}_n=kS_0\oplus D, which implies ∣kS0∣=∣S0∣|kS_0|=|S_0|. Now we claim that s−s′≠0(mod∣S0∣)s-s'\ne0\pmod{|S_0|} for any distinct s,s′∈S0s,s'\in S_0. Otherwise, if there exist some distinct s,s′∈S0s,s'\in S_0 such that s−s′≡0(mod∣S0∣)s-s'\equiv0\pmod{|S_0|}, then ks−ks′≡0(modk∣S0∣)ks-ks'\equiv0\pmod{k|S_0|}, that is, ks−ks′≡0(modn)ks-ks'\equiv0\pmod n. Therefore, ksks and ks′ks' are the same element in Zn\mathbb{Z}_n, and thus ∣kS0∣<∣S0∣|kS_0|<|S_0|, which is a contradiction. ■

In Theorem 3.2, if ∣S∣=pl−1|S|=p^l-1 with pl∣np^l\mid n and pl+1∤np^{l+1}\nmid n where pp is a prime and ll is a positive integer, then (pl,npl)=1\left(p^l,\frac{n}{p^l}\right)=1. Thus, Theorem 3.2 implies [7 Theorem 1.2]. Moreover, Theorem 3.2 also generalizes [5 Theorem 3.5].

Now by Lemma 2.5 and Theorem 3.2, one can easily observe the following result.

Corollary 3.3 Let SS be an inverse-closed subset of Zn∖{0}\mathbb{Z}_n \setminus\{0\} such that ∣S∣+1|S|+1 divides nn and is relatively prime to n∣S∣+1\frac{n}{|S|+1}. Then Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set if and only if it admits an efficient dominating set that is a subgroup of Zn\mathbb{Z}_n. In particular, if Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set, then every coset of the unique subgroup of order n∣S∣+1\frac{n}{|S|+1} in Zn\mathbb{Z}_n is an efficient dominating set.

The following theorem gives a complete structural description of efficient dominating sets in Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S), where ∣S∣+1|S|+1 divides nn and is relatively prime to n∣S∣+1\frac{n}{|S|+1}.

Theorem 3.4 Let SS be an inverse-closed subset of Zn∖{0}\mathbb{Z}_n \setminus\{0\} such that ∣S∣+1|S|+1 divides nn and is relatively prime to n∣S∣+1\frac{n}{|S|+1}. Suppose that Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set. Then the set D\mathcal{D} of all efficient dominating sets in Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) satisfies the following (i)-(ii):

(i) {i+∣S0∣Zn:i=0,1,⋯ ,∣S0∣−1}⊆D⊆{{i+kin∣S0∣:i=0,1,⋯ ,n∣S0∣−1}:∀ki∈{0,1,⋯ ,∣S0∣−1}}\{i+|S_0|\mathbb{Z}_n:i=0,1,\cdots,|S_0|-1\}\subseteq\mathcal{D}\subseteq\{\{i+k_i\frac{n}{|S_0|}:i=0,1,\cdots,\frac{n}{|S_0|}-1\}:\forall k_i\in\{0,1,\cdots,|S_0|-1\}\};

(ii) For any D∈DD\in\mathcal{D}, l∈Znl\in\mathbb{Z}_n, and any integer kk relatively prime to ∣D∣|D|, the set kD+l∈DkD+l\in\mathcal{D}.

Proof. (i) If Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set, then by Theorem 3.2, s−s′≠0(mod∣S0∣)s-s'\ne0\pmod{|S_0|} for any distinct s,s′∈S0s,s'\in S_0, and thus (S0−S0)∩(∣S0∣Zn−∣S0∣Zn)={0}(S_0-S_0)\cap(|S_0|\mathbb{Z}_n-|S_0|\mathbb{Z}_n)=\{0\}. Note that the cardinality of ∣S0∣Zn|S_0|\mathbb{Z}_n is n∣S0∣\frac{n}{|S_0|}. Therefore, by Proposition 2.1, Zn=S0⊕∣S0∣Zn\mathbb{Z}_n=S_0\oplus|S_0|\mathbb{Z}_n. By Lemma 2.2, ∣S0∣Zn∈D|S_0|\mathbb{Z}_n\in\mathcal{D}. Since for each i∈{0,1,⋯ ,∣S0∣−1}i\in\{0,1,\cdots,|S_0|-1\}, S0+(i+∣S0∣Zn)=i+(S0+∣S0∣Zn)=i+Zn=ZnS_0+(i+|S_0|\mathbb{Z}_n)=i+(S_0+|S_0|\mathbb{Z}_n)=i+\mathbb{Z}_n=\mathbb{Z}_n and the cardinality of i+∣S0∣Zni+|S_0|\mathbb{Z}_n is n∣S0∣\frac{n}{|S_0|}, it follows from proposition 2.1 that Zn=S0⊕(i+∣S0∣Zn)\mathbb{Z}_n=S_0\oplus(i+|S_0|\mathbb{Z}_n), and thus i+∣S0∣Zn∈Di+|S_0|\mathbb{Z}_n\in\mathcal{D}. Therefore, {i+∣S0∣Zn:i=0,1,⋯ ,∣S0∣−1}⊆D\{i+|S_0|\mathbb{Z}_n:i=0,1,\cdots,|S_0|-1\}\subseteq\mathcal{D}.

On the other hand, for any D∈DD\in\mathcal{D}, by Theorem 3.1, d≠d′(mod∣D∣)d\ne d'\pmod{|D|} for any distinct d,d′∈Dd,d'\in D. Since ∣D∣=n∣S0∣|D|=\frac{n}{|S_0|}, we may write D={d0,d1,⋯ ,dn∣S0∣−1}D=\{d_0,d_1,\cdots,d_{\frac{n}{|S_0|}-1}\} such that di≡i(modn∣S0∣)d_i\equiv i\pmod{\frac{n}{|S_0|}} for each i∈{0,1,⋯ ,n∣S0∣−1}i\in\{0,1,\cdots,\frac{n}{|S_0|}-1\}, and thus di=i+kin∣S0∣d_i=i+k_i\frac{n}{|S_0|}, where ki∈{0,1,⋯ ,∣S0∣−1}k_i\in\{0,1,\cdots,|S_0|-1\}. Hence D⊆{{i+kin∣S0∣:i=0,1,⋯ ,n∣S0∣−1}:∀ki∈{0,1,⋯ ,∣S0∣−1}}\mathcal{D}\subseteq\{\{i+k_i\frac{n}{|S_0|}:i=0,1,\cdots,\frac{n}{|S_0|}-1\}:\forall k_i\in\{0,1,\cdots,|S_0|-1\}\}.

(ii) For any D∈DD\in\mathcal{D}, by Lemma 2.2, Zn=S0⊕D\mathbb{Z}_n=S_0\oplus D. Since kk is relatively prime to ∣D∣|D|, it follows from Lemma 2.4 that Zn=S0⊕kD\mathbb{Z}_n=S_0\oplus kD, and thus Zn=S0⊕(kD+l)\mathbb{Z}_n=S_0\oplus(kD+l). Therefore, by Lemma 2.2, kD+l∈DkD+l\in\mathcal{D}. ■

:::

The following theorem extends the previous results to a more general setting and reduces the efficient domination problem in Zn\mathbb{Z}_n to the corresponding problem in the quotient group.

Theorem 3.5 Let SS be an inverse-closed subset of Zn∖{0}\mathbb{Z}_n \setminus\{0\} such that ∣S∣+1|S|+1 divides nn, and let m=(∣S0∣,n∣S0∣)m=(|S_0|,\frac{n}{|S_0|}). If (∣S0∣m,n∣S0∣)=1(\frac{|S_0|}{m},\frac{n}{|S_0|})=1, S0S_0 is periodic with stability subgroup AA such that ∣A∣=m|A|=m, set S0/A={A,t1+A,⋯ ,t∣S0∣m−1+A}S_0/A=\{A,t_1+A,\cdots,t_{\frac{|S_0|}{m}-1}+A\} and T0={t0,t1,⋯ ,t∣S0∣m−1}T_0=\{t_0,t_1,\cdots,t_{\frac{|S_0|}{m}-1}\} where t0=0t_0=0 and 1≤ti≤nm−11\leq t_i\leq\frac{n}{m}-1 for i∈{1,⋯ ,∣S0∣m−1}i\in\{1,\cdots,\frac{|S_0|}{m}-1\}, then Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set if and only if t−t′≠0(mod∣S0∣m)t-t'\ne0\pmod{\frac{|S_0|}{m}} for distinct t,t′∈T0t,t'\in T_0.

Proof. If Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set DD, then by Lemmas 2.2 and 2.3, Zn=S0⊕D\mathbb{Z}_n=S_0\oplus D, and thus Zn/A=S0/A⊕(D+A)/A\mathbb{Z}_n/A=S_0/A\oplus(D+A)/A, A∩(D−D)={0}A\cap(D-D)=\{0\}, it follows that Cay⁡(Zn/A,S0/A∖{A})\operatorname{Cay}(\mathbb{Z}_n/A,S_0/A\setminus\{A\}) admits an efficient dominating set (D+A)/A(D+A)/A, that is, Cay⁡(Zn/∣A∣,T0∖{0})\operatorname{Cay}(\mathbb{Z}_{n/|A|},T_0\setminus\{0\}) admits an efficient dominating set. Since ∣T0∣=∣S0∣m|T_0|=\frac{|S_0|}{m} and n∣T0∣=n∣S0∣\frac{n}{|T_0|}=\frac{n}{|S_0|}, it follows that ∣T0∣|T_0| is relatively prime to n∣T0∣\frac{n}{|T_0|}. By Theorem 3.2, t−t′≠0(mod∣S0∣m)t-t'\ne0\pmod{\frac{|S_0|}{m}} for any distinct t,t′∈T0t,t'\in T_0.

If t−t′≠0(mod∣S0∣m)t-t'\ne0\pmod{\frac{|S_0|}{m}} for any distinct t,t′∈T0t,t'\in T_0, then by Theorem 3.2, Cay⁡(Zn/∣A∣,T0∖{0})\operatorname{Cay}(\mathbb{Z}_{n/|A|},T_0\setminus\{0\}) admits an efficient dominating set, that is, Cay⁡(Zn/A,S0/A∖{A})\operatorname{Cay}(\mathbb{Z}_n/A,S_0/A\setminus\{A\}) admits an efficient dominating set, denoted by (D+A)/A(D+A)/A. Set (D+A)/A={d1+A,⋯ ,dn/∣S0∣+A}(D+A)/A=\{d_1+A,\cdots,d_{n/|S_0|}+A\} and set D={d1,⋯ ,dn/∣S0∣}D=\{d_1,\cdots,d_{n/|S_0|}\}. By Lemma 2.2, Zn/A=S0/A⊕(D+A)/A\mathbb{Z}_n/A=S_0/A\oplus(D+A)/A. Since ∣(D+A)/A∣=∣D∣=n∣S0∣|(D+A)/A|=|D|=\frac{n}{|S_0|}, it follows that A∩(D−D)={0}A\cap(D-D)=\{0\}. By Lemma 2.3, Zn=S0⊕D\mathbb{Z}_n=S_0\oplus D. Therefore, by Lemma 2.2, Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient dominating set DD.

Efficient open dominating sets

Now we turn to study efficient open dominating sets in circulant graphs.

Theorem 4.1 Let DD be a proper subset of Zn\mathbb{Z}_n such that ∣D∣|D| divides nn and is relatively prime to n∣D∣\frac{n}{|D|}. Then DD is an efficient open dominating set in some circulant graph Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) if and only if ∣D∣|D| is even and d−d′≠0(mod∣D∣)d-d'\ne0\pmod{|D|} for any distinct $d,d'\in D.

Proof. If ∣D∣|D| is even and d−d′≠0(mod∣D∣)d-d'\ne0\pmod{|D|} for any distinct d,d′∈Dd,d'\in D, then ((n2+∣D∣Zn)−(n2+∣D∣Zn))∩(D−D)={0}\left(\left(\frac{n}{2}+|D|\mathbb{Z}_n\right)-\left(\frac{n}{2}+|D|\mathbb{Z}_n\right)\right)\cap(D-D)=\{0\}. Note that the cardinality of n2+∣D∣Zn\frac{n}{2}+|D|\mathbb{Z}_n is n∣D∣\frac{n}{|D|}. Therefore, by Proposition 2.1, Zn=(n2+∣D∣Zn)⊕D\mathbb{Z}_n=\left(\frac{n}{2}+|D|\mathbb{Z}_n\right)\oplus D. Set S=n2+∣D∣ZnS=\frac{n}{2}+|D|\mathbb{Z}_n. Then SS is inverse-closed and Zn=S⊕D\mathbb{Z}_n=S\oplus D. Next we claim that 0∉S0\notin S. Otherwise, if 0∈S0\in S, then there exists some k∈{0,1,⋯ ,n∣D∣−1}k\in\{0,1,\cdots,\frac{n}{|D|}-1\} such that 0=n2+k∣D∣0=\frac{n}{2}+k|D|, and thus k∣D∣=n2k|D|=\frac{n}{2}, which implies that n∣D∣=2k\frac{n}{|D|}=2k. Therefore, ∣D∣|D| is not relatively prime to n∣D∣\frac{n}{|D|}, which is a contradiction. By Lemma 2.2, DD is an efficient open dominating set in the circulant graph Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S).

If DD is an efficient open dominating set in Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S), then by the definition of an efficient open dominating set, it is easy to see that DD induces a matching in Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S), and thus ∣D∣|D| is even. Moreover, if DD is an efficient open dominating set in Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S), then by Lemma 2.6, Zn=S⊕D\mathbb{Z}_n=S\oplus D. Similar to the proof of the ‘only if’ part in Theorem 3.1, we can obtain that d−d′≠0(mod∣D∣)d-d'\ne0\pmod{|D|} for any distinct d,d′∈Dd,d'\in D.

Using Lemmas 2.6 and 2.7 and following the proof of Theorem 3.2 but with S0S_0 replaced by SS, one can prove the following result, which also implies [7 Theorem 1.4] and [2 Theorems 5.4–5.6].

Theorem 4.2 Let SS be an inverse-closed subset of Zn∖{0}\mathbb{Z}_n \setminus\{0\} such that ∣S∣|S| divides nn and ∣S∣|S| is relatively prime to n∣S∣\frac{n}{|S|}. Then Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient open dominating set if and only if s−s′≠0(mod∣S∣)s-s' \ne0 \pmod{|S|} for distinct s,s′∈Ss,s' \in S.

By Lemma 2.7 and Theorem 4.2, one can easily observe the following result.

Corollary 4.3 Let SS be an inverse-closed subset of Zn∖{0}\mathbb{Z}_n \setminus\{0\} such that ∣S∣|S| divides nn and ∣S∣|S| is relatively prime to n∣S∣\frac{n}{|S|}. Then Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) either doesn’t admit any efficient open dominating set or admits an efficient open dominating set which is a subgroup of Zn\mathbb{Z}_n.

Note that every finite abelian group is a direct product of some cyclic groups. By Lemma 2.6, we can obtain the following corollary which generalizes the result of Theorem 4.2 about circulant graphs by giving a similar result about Cayley graphs on abelian groups.

Corollary 4.4 Let GG be an abelian group and write G=Zn1×⋯×ZnkG = \mathbb{Z}_{n_1} \times\cdots\times\mathbb{Z}_{n_k}, where kk and n1,…,nkn_1,\ldots,n_k are positive integers, let S=S1×⋯×SkS = S_1 \times\cdots\times S_k, where SiS_i is an inverse-closed subset of Zni∖{0}\mathbb{Z}_{n_i} \setminus\{0\} such that ∣Si∣|S_i| divides nin_i and ∣Si∣|S_i| is relatively prime to ni∣Si∣\frac{n_i}{|S_i|} for each i∈{1,…,k}i \in\{1,\ldots,k\}. Then Cay⁡(G,S)\operatorname{Cay}(G,S) admits an efficient open dominating set if and only if si−si′≠0(mod∣Si∣)s_i-s'_i \ne0 \pmod{|S_i|} for distinct si,si′∈Sis_i,s'_i \in S_i and each i∈{1,…,k}i \in\{1,\ldots,k\}.

Using Lemmas 2.4 and 2.6 and following the proof of Theorem 3.4 but with S0S_0 replaced by SS, we can prove the following result.

Theorem 4.5 Suppose that Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) admits an efficient open dominating set. Then the set D\mathbb{D} of all efficient open dominating sets of Cay⁡(Zn,S)\operatorname{Cay}(\mathbb{Z}_n,S) satisfies the following (i)-(ii):

(i) {i+∣S∣Zn:i=0,1,…,∣S∣−1}⊆D⊆{{i+kin∣S∣:i=0,1,…,n∣S∣−1}:∀ki∈{0,1,…,∣S∣−1}}\{i+|S|\mathbb{Z}_n: i=0,1,\ldots,|S|-1\} \subseteq\mathbb{D} \subseteq\{\{i+k_i\frac{n}{|S|}: i=0,1,\ldots,\frac{n}{|S|}-1\}: \forall k_i \in\{0,1,\ldots,|S|-1\}\};

(ii) For any D∈DD \in\mathbb{D}, l∈Znl \in\mathbb{Z}_n, and any integer kk relatively prime to ∣D∣|D|, the set kD+l∈DkD+l \in\mathbb{D}.

Conflict of interest

The authors declare that there are no conflicts of interest.

References

[1] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 288–296.

References

  1. [1]N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 288–296.DOI
  2. [2]P. J. Cameron, R. S. Yap, S. Zhou, Perfect codes in Cayley graphs of abelian groups, Des. Codes Cryptogr. 94 (2026), 87.DOI
  3. [3]I. J. Dejter, O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003) 319–328.DOI
  4. [4]Y. P. Deng, Efficient dominating sets in circulant graphs with domination number prime, Inform. Process. Lett. 114 (2014) 700–702.DOI
  5. [5]Y. P. Deng, Y. Q. Sun, Q. Liu, H. C. Wang, Efficient dominating sets in circulant graphs, Discrete Math. 340 (2017) 1503–1507.DOI
  6. [6]Y. Q. Feng, R. X. Hao, Y. S. Kwon, J. Lee, On perfect dominating sets in Cayley graphs, Discrete Appl. Math. 376 (2025) 160–166.DOI
  7. [7]R. Q. Feng, H. Huang, S. M. Zhou, Perfect codes in circulant graphs, Discrete Math. 340 (2017) 1522–1527.DOI
  8. [8]H. Huang, B. Z. Xia, S. Zhou, Perfect codes in Cayley graphs, SIAM J. Discrete Math. 32 (2018) 548–559.arxiv.org/abs/1609.03755
  9. [9]J. Kratochvíl, Perfect codes of graphs, J. Combin. Theory Ser. B 40 (1986) 224-228.DOI
  10. [10]K. R. Kumar, G. MacGillivray, Efficient domination in circulant graphs, Discrete Math. 313 (2013) 767–771.DOI
  11. [11]J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37 (2001) 213–219.DOI
  12. [12]N. Obradović, J. Peters, G. Ružić, Efficient domination in circulant graph with two chord lengths, Inform. Process. Lett. 102 (2007) 253–258.
  13. [13]S. Szabó, A. D. Sands, Factoring Groups into Subsets, CRC Press, Boca Raton, 2009.DOI
  14. [14]S. Terada, Perfect codes in SL(2, 2^f), European J. Combin. 25 (2004) 1077–1085.
  15. [15]D. T. Vuza, Supplementary sets and regular complementary unending canons (Part One), Perspect. New Music 29 (1991) 22–49.DOI
  16. [16]X. Wang, O. Serra, S. J. Xu, S. Zhou, Perfect codes in circulant graphs of degree p^l − 1, arXiv:2403.02205 [math.CO], 2024.arxiv.org/abs/2403.02205

Paper details

vlnc:W_qnc5nprp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 13

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents