TY - JOUR

T1 - Domination ratio of a family of integer distance digraphs with arbitrary degree

AU - Huang, Jia

N1 - Funding Information:
The author thanks Christian Gaetz for helpful conversations on sets of integers with missing differences, and also thanks an anonymous referee for providing valuable comments and suggestions on the manuscript.
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/8/15

Y1 - 2022/8/15

N2 - An integer distance digraph is the Cayley graph Γ(Z,S) of the additive group Z of all integers with respect to a finite subset S⊆Z. The domination ratio of Γ(Z,S), defined as the minimum density of its dominating sets, is related to some number theory problems, such as tiling the integers and finding the maximum density of a set of integers with missing differences. We precisely determine the domination ratio of the integer distance graph Γ(Z,{1,2,…,d−2,s}) for any integers d and s satisfying d≥2 and s∉[0,d−2]. Our result generalizes a previous result on the domination ratio of the graph Γ(Z,{1,s}) with s∈Z∖{0,1} and also implies the domination number of certain circulant graphs Γ(Zn,S), where Zn is the finite cyclic group of integers modulo n and S is a subset of Zn.

AB - An integer distance digraph is the Cayley graph Γ(Z,S) of the additive group Z of all integers with respect to a finite subset S⊆Z. The domination ratio of Γ(Z,S), defined as the minimum density of its dominating sets, is related to some number theory problems, such as tiling the integers and finding the maximum density of a set of integers with missing differences. We precisely determine the domination ratio of the integer distance graph Γ(Z,{1,2,…,d−2,s}) for any integers d and s satisfying d≥2 and s∉[0,d−2]. Our result generalizes a previous result on the domination ratio of the graph Γ(Z,{1,s}) with s∈Z∖{0,1} and also implies the domination number of certain circulant graphs Γ(Zn,S), where Zn is the finite cyclic group of integers modulo n and S is a subset of Zn.

KW - Cayley graph

KW - Circulant graph

KW - Domination ratio

KW - Efficient dominating set

KW - Integer distance graph

KW - Integer tiling

UR - http://www.scopus.com/inward/record.url?scp=85129721549&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85129721549&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2022.04.011

DO - 10.1016/j.dam.2022.04.011

M3 - Article

AN - SCOPUS:85129721549

SN - 0166-218X

VL - 317

SP - 1

EP - 9

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -