Paired-domination game played on cycles (Q6103482)

This text further develops the graph domination game introduced in [\textit{B. Brešar} et al. SIAM J. Discrete Math. 24, No. 3, 979--991 (2010; Zbl 1223.05189)]. The version of the game studied involves two players, the Dominator and the Staller, who take turns choosing pairs of adjacent, unchosen vertices that dominate at least one vertex not dominated by a previously chosen pair of vertices. The game ends when there are no moves left, and the resulting set of vertices becomes a paired-dominating set -- a dominating set such that the subgraph induced by it contains a perfect matching. The Staller aims to maximize the cardinality of this set while the Dominator wishes to minimize it. The paper begins with both previous and new bounds for the game paired-domination number, then introduces the Paired-Domination Continuation principle and uses it to prove that for every graph \(G\), \(|\gamma_{gpr}(G)-\gamma_{gpr}^\prime (G)|\in\{0, 2\}\) where \(\gamma_{gpr}(G)\) is the cardinality of the dominating set when the Dominator moves first and \(\gamma_{gpr}^\prime (G)\) is the same quantity when the Staller moves first. The paper then introduces exact values for \(\gamma_{gpr}(G)\) and \(\gamma_{gpr}^\prime (G)\) where \(G\) is a cycle \(C_n\) on \(n\) vertices.