Paperlane

no. 4 · Wednesday 28 October 2026

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

Yun-Ping Deng and Xuanlong Ma

math.CO · 9 pp

Abstract

Let $D$ be a proper subset of $\mathbb{Z}_n$ such that $|D|$ divides $n$ and is relatively prime to $\frac{n}{|D|}$. We first establish a necessary and sufficient condition for $D$ to be an efficient dominating set of some circulant graph $\Cay(\mathbb{Z}_n,S)$. Moreover, for an inverse-closed subset $S$ of $\mathbb{Z}_n\setminus\{0\}$ such that $|S|+1$ divides $n$ and is relatively prime to $\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].

comments
9 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.37167 ↗