WorksMathematics
Notes on efficient dominating sets and efficient open dominating sets in circulant graphs
Abstract
Let be a proper subset of such that divides and is relatively prime to . We first establish a necessary and sufficient condition for to be an efficient dominating set of some circulant graph \Cay(\mathbb{Z}_n,S). Moreover, for an inverse-closed subset of such that divides and is relatively prime to , 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 be a finite group with identity element and an inverse-closed subset of not containing . The Cayley graph on with respect to the connection set is defined as the graph with vertex set and edge set and denoted by . A Cayley
E-mail addresses: [email protected] (Deng), [email protected] (Ma) graph on finite cyclic group with addition modulo is called a circulant graph.
A subset of vertices in a graph is called an efficient dominating set (also called a perfect code) if is an independent set and each vertex not in is adjacent to exactly one vertex in . By the definitions of a circulant graph and an efficient dominating set, it is easy to see that if admits an efficient dominating set , then . A subset of vertices in a graph is called an efficient open dominating set (also called a total perfect code) if each vertex in is adjacent to exactly one vertex in . Similarly, one can easily see that if admits an efficient open dominating set , then , and induces a matching in , which implies that 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 -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 () 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 ( prime and 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 of degree , and ( primes and positive integer) or order , , , , ( distinct primes and positive integer) satisfying that divides and is relatively prime to . 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 of degree . ( prime and positive integer) satisfying that divides and is relatively prime to .
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 , where is a prime and , 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 of general degree and general order satisfying that divides and is relatively prime to . 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 be a finite abelian group with additive notation, and let be two subsets of . If every has a unique representation in the form with , , then is called the direct sum of and . In this case, we write . For two positive integers , we use to denote the greatest common divisor of and . If , then and are relatively prime.
Proposition 2.1 ([15 Proposition 2.1]) Let be a finite abelian group and let be subsets of . Then is equivalent to the conjunction of any two of the following conditions:
(i) ;
(ii) ;
(ii) .
If is a subset of a finite abelian group , then we write .
Lemma 2.2 ([4 Lemma 2.3]) A subset of finite abelian group is an efficient dominating set of if and only if .
For any subset of an abelian group , the set of all satisfying is a subgroup of , called the stability subgroup of , denoted by . It is easy to see that is a union of cosets of . Moreover, if , then . A subset is called periodic if . Otherwise, a subset is called aperiodic if .
Lemma 2.3 ([4 Lemma 2.4]) Let and be two subsets of finite abelian group , and let . Then if and only if and .
Lemma 2.4 ([13 Theorem 3.17]) Let be a finite abelian group, and let be subsets of . If , then for any integer relatively prime to , where .
The following result was first stated in [12 Remark 1] and also appears in [4].
Lemma 2.5 ([12 Remark 1]) Let , where is an integer. Then admits an efficient dominating set which is a coset of some subgroup of if and only if for any distinct , where .
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 of a finite abelian group is an efficient open dominating set of if and only if .
Similar to Lemma 2.5, we have the following result.
Lemma 2.7 Let , where is an integer. Then admits an efficient open dominating set which is a coset of some subgroup of if and only if for any distinct .
Efficient dominating sets
Clearly, if admits an efficient dominating set , then . We first establish a necessary and sufficient condition for a proper subset of with and to be an efficient dominating set of .
Theorem 3.1 Let be a proper subset of such that divides and is relatively prime to . Then is an efficient dominating set of some circulant graph if and only if for distinct .
Proof. Suppose that for distinct . Then
Note that the cardinality of is . Therefore, by Proposition 2.1, . Now let . Then is inverse-closed and , where . By Lemma 2.2, is an efficient dominating set in , as desired.
Conversely, suppose that is an efficient dominating set in . Then by Lemma 2.2, , where . Set . Then and is relatively prime to . It follows from Lemma 2.4 that , which implies that . Now we claim that for any distinct . Otherwise, if there exist some distinct such that , then , that is, . Therefore, and are the same element in , and thus , which is a contradiction. ■
If is an inverse-closed subset of such that and , then the following result gives a necessary and sufficient condition for which admits an efficient dominating set.
Theorem 3.2 Let be an inverse-closed subset of such that divides and is relatively prime to . Then admits an efficient dominating set if and only if for distinct .
Proof. If for distinct , then by Lemma 2.5, admits an efficient dominating set.
For the converse, suppose that admits an efficient dominating set . Then by Lemma 2.2, . Set . Then and is relatively prime to . It follows from Lemma 2.4 that , which implies . Now we claim that for any distinct . Otherwise, if there exist some distinct such that , then , that is, . Therefore, and are the same element in , and thus , which is a contradiction. ■
In Theorem 3.2, if with and where is a prime and is a positive integer, then . 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 be an inverse-closed subset of such that divides and is relatively prime to . Then admits an efficient dominating set if and only if it admits an efficient dominating set that is a subgroup of . In particular, if admits an efficient dominating set, then every coset of the unique subgroup of order in is an efficient dominating set.
The following theorem gives a complete structural description of efficient dominating sets in , where divides and is relatively prime to .
Theorem 3.4 Let be an inverse-closed subset of such that divides and is relatively prime to . Suppose that admits an efficient dominating set. Then the set of all efficient dominating sets in satisfies the following (i)-(ii):
(i) ;
(ii) For any , , and any integer relatively prime to , the set .
Proof. (i) If admits an efficient dominating set, then by Theorem 3.2, for any distinct , and thus . Note that the cardinality of is . Therefore, by Proposition 2.1, . By Lemma 2.2, . Since for each , and the cardinality of is , it follows from proposition 2.1 that , and thus . Therefore, .
On the other hand, for any , by Theorem 3.1, for any distinct . Since , we may write such that for each , and thus , where . Hence .
(ii) For any , by Lemma 2.2, . Since is relatively prime to , it follows from Lemma 2.4 that , and thus . Therefore, by Lemma 2.2, . ■
:::
The following theorem extends the previous results to a more general setting and reduces the efficient domination problem in to the corresponding problem in the quotient group.
Theorem 3.5 Let be an inverse-closed subset of such that divides , and let . If , is periodic with stability subgroup such that , set and where and for , then admits an efficient dominating set if and only if for distinct .
Proof. If admits an efficient dominating set , then by Lemmas 2.2 and 2.3, , and thus , , it follows that admits an efficient dominating set , that is, admits an efficient dominating set. Since and , it follows that is relatively prime to . By Theorem 3.2, for any distinct .
If for any distinct , then by Theorem 3.2, admits an efficient dominating set, that is, admits an efficient dominating set, denoted by . Set and set . By Lemma 2.2, . Since , it follows that . By Lemma 2.3, . Therefore, by Lemma 2.2, admits an efficient dominating set .
Efficient open dominating sets
Now we turn to study efficient open dominating sets in circulant graphs.
Theorem 4.1 Let be a proper subset of such that divides and is relatively prime to . Then is an efficient open dominating set in some circulant graph if and only if is even and for any distinct $d,d'\in D.
Proof. If is even and for any distinct , then . Note that the cardinality of is . Therefore, by Proposition 2.1, . Set . Then is inverse-closed and . Next we claim that . Otherwise, if , then there exists some such that , and thus , which implies that . Therefore, is not relatively prime to , which is a contradiction. By Lemma 2.2, is an efficient open dominating set in the circulant graph .
If is an efficient open dominating set in , then by the definition of an efficient open dominating set, it is easy to see that induces a matching in , and thus is even. Moreover, if is an efficient open dominating set in , then by Lemma 2.6, . Similar to the proof of the ‘only if’ part in Theorem 3.1, we can obtain that for any distinct .
Using Lemmas 2.6 and 2.7 and following the proof of Theorem 3.2 but with replaced by , one can prove the following result, which also implies [7 Theorem 1.4] and [2 Theorems 5.4–5.6].
Theorem 4.2 Let be an inverse-closed subset of such that divides and is relatively prime to . Then admits an efficient open dominating set if and only if for distinct .
By Lemma 2.7 and Theorem 4.2, one can easily observe the following result.
Corollary 4.3 Let be an inverse-closed subset of such that divides and is relatively prime to . Then either doesn’t admit any efficient open dominating set or admits an efficient open dominating set which is a subgroup of .
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 be an abelian group and write , where and are positive integers, let , where is an inverse-closed subset of such that divides and is relatively prime to for each . Then admits an efficient open dominating set if and only if for distinct and each .
Using Lemmas 2.4 and 2.6 and following the proof of Theorem 3.4 but with replaced by , we can prove the following result.
Theorem 4.5 Suppose that admits an efficient open dominating set. Then the set of all efficient open dominating sets of satisfies the following (i)-(ii):
(i) ;
(ii) For any , , and any integer relatively prime to , the set .
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]N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 288–296.DOI
- [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]I. J. Dejter, O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003) 319–328.DOI
- [4]Y. P. Deng, Efficient dominating sets in circulant graphs with domination number prime, Inform. Process. Lett. 114 (2014) 700–702.DOI
- [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]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]R. Q. Feng, H. Huang, S. M. Zhou, Perfect codes in circulant graphs, Discrete Math. 340 (2017) 1522–1527.DOI
- [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]J. Kratochvíl, Perfect codes of graphs, J. Combin. Theory Ser. B 40 (1986) 224-228.DOI
- [10]K. R. Kumar, G. MacGillivray, Efficient domination in circulant graphs, Discrete Math. 313 (2013) 767–771.DOI
- [11]J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37 (2001) 213–219.DOI
- [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]S. Szabó, A. D. Sands, Factoring Groups into Subsets, CRC Press, Boca Raton, 2009.DOI
- [14]S. Terada, Perfect codes in SL(2, 2^f), European J. Combin. 25 (2004) 1077–1085.
- [15]D. T. Vuza, Supplementary sets and regular complementary unending canons (Part One), Perspect. New Music 29 (1991) 22–49.DOI
- [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