On the \(k\)-domination number, the domination number and the cycle of length four (Q2811813)

The \(k\)-domination number \(\gamma_k(G)\) of a graph \(G\) is the minimum cardinality of a \(k\)-dominating set of \(G\), where a subset \(D\) of vertices of \(G\) is \(k\)-dominating if every vertex not in \(D\) has at least \(k\) neighbors in \(D\). It is known that if \(\delta(G) \geq k \geq 2\), then \(\gamma_k(G) \geq \gamma(G)+k-2\). In this paper, the structure of graphs satisfying the equality \(\gamma_k(G) \geq \gamma(G)+k-2\) is investigated. The main results proved for such graphs \(G\) are: (i) every vertex of \(G\) lies on an induced cycle of length 4 and (ii) \(G\) contains at least \((\gamma(G)-1)(k-1)\) induced cycles of length 4. The author also demonstrates that the bound in (ii) is sharp.