Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 42 min ago
PreprintCC BY 4.0arXiv

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

  • Yun-Ping Deng
  • Xuanlong Ma
Open at sourcePDFDOICite

Abstract

Let D be a proper subset of ℤn such that |D| divides n and is relatively prime to n/|D|. We first establish a necessary and sufficient condition for D to be an efficient dominating set of some circulant graph Cay(ℤn,S). Moreover, for an inverse-closed subset S of ℤn∖{0} such that |S|+1 divides n and is relatively prime to n/(|S|+1), we give a necessary and sufficient condition for the existence of efficient dominating sets in Cay(ℤ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].

Related

  1. Existence of regular sets in circulant quartic graphs: a complete characterization
    A. Abdollahi, J. Bagherian, F. Jafari +3
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Every cubic graph has four total dominating sets covering each vertex at most twice
    Hyemin Kwon, Boram Park, Yoshio Sano
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Prime Nullspace Matrices and Even Dominating Sets
    William F. Klostermeyer
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Total dominating sets and four-colorings of planar triangulations
    Hyemin Kwon, Boram Park, Yoshio Sano
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. On the local average order of dominating sets
    Tingyun Chen, Weihua He, Hong-Jian Lai +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{deng2026notes,
  title = {{Notes on efficient dominating sets and efficient open dominating sets in circulant graphs}},
  author = {Yun-Ping Deng and Xuanlong Ma},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.37167},
  eprint = {2610.37167},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.37167},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Notes on efficient dominating sets and efficient open dominating sets in circulant graphs
AU  - Yun-Ping Deng
AU  - Xuanlong Ma
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.37167
UR  - https://arxiv.org/abs/2610.37167
AB  - Let D be a proper subset of ℤ_n such that |D| divides n and is relatively prime to n/|D|. We first establish a necessary and sufficient condition for D to be an efficient dominating set of some circulant graph Cay(ℤ_n,S). Moreover, for an inverse-closed subset S of ℤ_n∖{0} such that |S|+1 divides n and is relatively prime to n/(|S|+1), we give a necessary and sufficient condition for the existence of efficient dominating sets in Cay(ℤ_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].
ER  -