## Abstract

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 Γ(Z_{n},S), where Z_{n} is the finite cyclic group of integers modulo n and S is a subset of Z_{n}.

Original language | English (US) |
---|---|

Pages (from-to) | 1-9 |

Number of pages | 9 |

Journal | Discrete Applied Mathematics |

Volume | 317 |

DOIs | |

State | Published - Aug 15 2022 |

## Keywords

- Cayley graph
- Circulant graph
- Domination ratio
- Efficient dominating set
- Integer distance graph
- Integer tiling

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics