Notes on efficient dominating sets and efficient open dominating sets in circulant graphs
math.CO
Submitted: 2026-10-27
Updated: 2026-10-27
Comments: 9 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: Let D be a proper subset of Z n such that D divides n and is relatively prime to n over D.
Abstract
Let D be a proper subset of Z n such that D divides n and is relatively prime to n over D. We first establish a necessary and sufficient condition for D to be an efficient dominating set of some circulant graph (Z n,S). Moreover, for an inverse-closed subset S of Z n 0 such that S+1 divides n and is relatively prime to n over S+1, we give a necessary and sufficient condition for the existence of efficient dominating sets in (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].
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality