Constructing dominating sets in circulant graphs (Q1745909)

A subset \(D\) of the vertex set of a directed graph \(G\) is called a {it dominating set} of \(G\) if every vertex \(w\) of \(G\) not in \(D\) is adjacent from a vertex \(v\) of \(D\), i.e., \((v,w)\) is an arc of \(G\). Recall that a circulant graph (actually a directed graph) can be constructed as follows: Given a subset \(S\) of \(Z_n\), we define the graph \(C_n(S)\) to be the directed graph with vertex set \(Z_n\), where for \(i\), \(j\) in \(Z_n\) there is an edge from \(i\) to \(j\) if and only if \(i-j\) is in \(S\). Clearly, \(C_n(S)\) is an \(n\)-vertex \(k\)-regular graph, where \(k\) is the order of \(S\). The authors give efficient constructions of ``reasonably small'' dominationg sets of various types in circulant graphs on \(n\) nodes and \(k\) distinct chord lengths. The structure of the cyclic group underlying a circulant graph makes these graphs suitable for applications of methods of analytic number theory.