Minimum 2-dominating sets in regular graphs (Q2091810)

Let \(G=(V,E)\) be a simple graph. A dominating set of \(G\) is a subset \(D\subseteq V\) such that every vertex not in \(D\) is adjacent to at least one vertex in \(D\). The cardinality of the smallest dominating set of \(G\), denoted by \(\gamma(G)\), is the domination number of \(G\). This may be generalized as follows. Let \(k\geq 1\) be an integer. A set \(D_k \subseteq V(G)\) is a \(k\)-dominating set of graph \(G\) if every vertex in \(V(G) \setminus D_k\) is adjacent to at least \(k\) vertices of \(G\). The \(k\)-domination number \(\gamma_k(G)\) is the smallest possible cardinality of such a set \(D_k\). The authors in this work, for any fixed \(d \geq 3\), obtained upper bounds, valid asymptotically almost surely for random \(d\)-regular graphs, on \(\frac{\gamma_2(G)}{|V(G)|}\) as a function of \(d\).