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

Abstract

An integer distance digraph is the Cayley graph $\Gamma (\mathbb{Z},S)$ of the additive group $\mathbb{Z}$ of all integers with respect to a finite subset $S\subseteq \mathbb{Z}$. The domination ratio of $\Gamma (\mathbb{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 $\Gamma (\mathbb{Z},\{1,2,\dots ,d-2,s\})$ for any integers $d$ and $s$ satisfying $d\ge 2$ and $s\notin [0,d-2]$. Our result generalizes a previous result on the domination ratio of the graph $\Gamma (\mathbb{Z},\{1,s\})$ with $s\in \mathbb{Z}\setminus \{0,1\}$ and also implies the domination number of certain circulant graphs $\Gamma ({\mathbb{Z}}_n,S)$, where ${\mathbb{Z}}_n$ is the finite cyclic group of integers modulo $n$ and $S$ is a subset of ${\mathbb{Z}}_n$.

11 pages. arXiv admin note: text overlap with arXiv:1903.01844