On (1,2)-domination in cubic graphs (Q2043407)

A cubic graph is a graph in which every vertex in the graph has a degree of three. For integers \(r \geq 1\) and \(s \geq 1\), an \((r, s)\)-dominating set of a graph \(G\) with minimum degree at least \(s\) is a set \(S\) of vertices such that every vertex in \(V(G) - S\) has at least \(r\) neighbors in \(S\) and every vertex in \(S\) has at least \(s\) neighbors in \(S\). The \((r, s)\)-domination number, denoted \(\gamma_{r, s}(G)\), of \(G\) is the minimum cardinality of an \((r, s)\)-dominating set of \(G\). In this paper, the authors prove that \(\gamma_{1, 2}(G) \leq \frac{3}{4}n\) if \(G\) is a cubic graph of order \(n\) and the bound is tight.