Domination ratio of a family of integer distance digraphs with arbitrary degree (Q2142680): Difference between revisions

A Cayley graph \(\Gamma(G,S)\) is determined by a group \(G\) and a subset \(S \subseteq G\). The vertex set of \(\Gamma(G,S)\) is \(G\) and the edge set of \(\Gamma(G,S)\) consists of ordered pairs \((g,gs)\) for all \(g\in G\) and \(s\in S\). 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 \(\overline{\gamma}(\mathbb{Z},S)\) of \(\Gamma(\mathbb{Z},S)\) is defined as the infimum of the (lower) density \[\delta(D):=\lim_{n\rightarrow +\infty}\inf\frac{|D\cap [-n,n]|}{2n+1}\] overall dominating sets \(D\) of \(\Gamma(\mathbb{Z},S)\). This concept 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. In this paper, the precise value of \(\overline{\gamma}(\mathbb{Z},S)\) where \(S=\{1,2,\dots,d-2,s\}\), \(d\ge 2\) and \(s\notin[0,d-2]\) is determined as \[ \begin{split} \overline{\gamma}(\mathbb{Z},\{1,2,\dots,d-2,s\}) &=\min \{ \frac{k+1}{dk+e}, \frac{2k+e-1}{2dk-d+2e}, \frac{1}{d-1}\} \\ &= \left\{ \begin{array} {l l} (k+1)/(dk+e), & \mbox{if}\ e\ge 2, d\le k+e+1, \\ (2k+e-1)/(2dk-d+2e), & \mbox{if}\ e=1, d\le 2k+2, \\ 1/(d-1), & \mbox{otherwise,} \end{array}\right. \end{split} \] where \(s\) is written as \(s = dk + e - 1\) or \(s = -dk+d-e-1\) for some integer \(k\ge 1\) and \(e\in \{1, \dots, d-1\}\).