Paired-domination game played on cycles (Q6103482)
From MaRDI portal
scientific article; zbMATH DE number 7691775
Language | Label | Description | Also known as |
---|---|---|---|
English | Paired-domination game played on cycles |
scientific article; zbMATH DE number 7691775 |
Statements
Paired-domination game played on cycles (English)
0 references
5 June 2023
0 references
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.
0 references
domination game
0 references
optimization game
0 references
paired-domination game
0 references
paired-domination number
0 references
competitive optimization
0 references
0 references