The Normal Play of the Domination Game

J. M. Brito, N. Martins, R. Sampaio · 2025

Read The Normal Play of the Domination Game by J. M. Brito, N. Martins, R. Sampaio (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-13118.txt.

Introduction

João Marcos Brito and co-authors study the normal play version of the domination game in this 2025 mathematics paper. The domination game is played on a graph, where players claim points that cover the graph step by step. In the older optimization variant, players work together to finish fast, and a famous three fifths conjecture about it was settled in 2024. Normal play flips the goal: two players compete, and the last to move wins.

The authors prove this version is PSPACE-complete, even on graphs with diameter two. Using Sprague-Grundy theory, they solve paths and cycles exactly. On a path, the first player wins unless the length is a multiple of four. On a cycle, the first player wins only for lengths of the form 4k+3. They also give a fast method to call the winner on mixes of paths and cycles.

Catalog record

CREATORJ. M. Brito, N. Martins, R. Sampaio
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-13118

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Normal Play of the Domination Game J. M. Brito, N. Martins, R. Sampaio Abstract In 2010, Brešar, Klavžar and Rall introduced the optimization variant of the graph domination game and the game domination number. In 2024, Leo Versteegen obtained the celebrated proof of the Conjecture 3 5 \frac{3}{5} on this variant of the domination game, proposed by Kinnersley, West and Zamani in 2013. In this paper, we investigate for the first time the normal play of the domination game, which we call Normal Domination Game , that is an impartial game where the last to play wins. We use the Sprague-Grundy theory to prove that Alice (the first player) wins in the path P n P_{n} if and only if n n is not a multiple of 4 4 , and wins in the cycle C n C_{n} if and only if n = 4 ​ k + 3 n=4k+3 for some integer k k . We also obtain a polynomial time algorithm to decide the winner for any disjoint union of paths and cycles in the Normal Domination Game and its natural partizan variant. Keywords: Domination game, normal variant, Sprague-Grundy theory. 1 Introduction Two of the most studied structures in graph theory are the independent sets and the dominating sets. Given a graph G and a set S of vertices, we say that S is independent if there is no edge between the vertices of S and we say that S is a dominating set if every vertex of G is in S or has a neighbor in S . The independence number \alpha(G) and the domination number \gamma(G) are classic graph parameters, among the most investigated, consisting of the sizes of a maximum independence set and a minimum dominating set of the graph, respectively. These parameters were exhaustively investigated in the literature and are known to be NP-hard even in restricted graph classes. In this paper, we deal with the game variants of these problems. The game variant of the independence set problem was introduced in 1908 by Henry Dudeney [ 5 ] as the Kayles game in which two players, Alice and Bob, alternately select vertices of a path graph P_{n} in such a way that the set of selected vertices is an independent set. The Kayles game is in the normal play convention , that is, the last to play wins. In the misère play convention , the last to play loses and the game is called Misère Kayles . The Kayles game was solved in 1956 by Guy and Smith [ 7 ] through the Sprague-Grundy theory. The generalization of the Kayles game to any graph G was denoted by Node Kayles game and was proved PSPACE-hard by Schaefer [ 11 ] in 1978. In 2002, Bodlander and Kratsch [ 2 ] proved that the Node Kayles game is polynomial time solvable in several graph classes, such as cographs, cocomparability graphs and circular arc graphs. In 2001, the optimization variant of the Node Kayles game was introduced [ 10 ] , in which Alice wants to maximize the number of selected vertices and Bob wants to minimize this number. The game independence number \alpha_{g}(G) is the maximum number of selected vertices in the game with best play for Alice and Bob. Curiously, this optimization variant of the Node Kayles game and the game independence number \alpha_{g}(G) have been little studied in the literature. The game variant of the dominating set problem was introduced much later, in 2010, by Brešar, Klavžar and Rall [ 4 ] , called as the Domination Game . In this game, Alice and Bob alternately select vertices of a graph G in such a way that every vertex selected in the game must dominate at least one vertex that was not dominated before. The game ends when the selected vertices form a dominating set. To the best of our knowledge, this game was investigated only in the optimization variant , in which Alice wants to minimize the number of selected vertices and Bob wants to maximize this number. The game domination number \gamma_{g}(G) is the minimum number of selected vertices in the game with best play for Alice and Bob. This parameter was intensively investigated. In 2013, Kinnersley, West, and Zamani [ 9 ] proved the Theorem 2/3 and proposed the Conjecture 3/5 on the Domination Game . They state that \gamma_{g}(G) is at most \frac{2}{3}n and \frac{3}{5}n , respectively, if G has no isolated vertices. Eleven years later, in 2024, Versteegen [ 13 ] obtained the celebrated proof of the Conjecture 3/5 , which is now called the Theorem 3/5 . Our Contributions. In this paper, we start the investigation of the normal play of the domination game (the last to play wins), which we call Normal Domination Game . We use the Sprague-Grundy theory to prove that Alice (the first player) wins in the path P_{n} if and only if n\%4\neq 0 ( n is not a multiple of 4 ), and wins in the cycle C_{n} if and only if n\%4=3 , where \% is the remainder operation (mod). We also determine in polynomial time the winner for any disjoint union of paths and cycles in the Normal Domination Game and its natural partizan variant, using the Combinatorial Game Theory. We conclude with some open questions. 2 Impartial game in paths and cycles In this section, we use the Sprague-Grundy theory to solve the Normal Domination Game in paths and cycles. In order to do this, we need to explain some technical details of the Sprague-Grundy theory, which is focused on the normal play of impartial games such as the Normal Domination Game . 2.1 Nimbers and the Sprague-Grundy Theory We say that a two-person combinatorial game is impartial if the set of moves available from any given position (or configuration) is the same for both players. It is easy to see that the Normal Domination Game is impartial. Nim is one of the most important impartial games in which two players take turns removing objects from disjoint heaps until there are no objects remaining. On each turn, a player chooses a non empty heap and must remove a positive number of objects from this heap. An instance of Nim is given by a sequence \Phi=(h_{1},h_{2},\ldots,h_{k}) , where k is the number of heaps and h_{i}\geq 1 is the i -th heap’s size. Nim plays a fundamental role in the Sprague-Grundy game theory and was mathematically solved [ 3 ] by Bouton in 1901 for any instance \Phi . In other words, the decision problem of deciding which player has a winning strategy is polynomial time solvable in both Nim variants. This is related to nim-sum (\Phi)=h_{1}\oplus\ldots\oplus h_{k} , where \oplus is the bitwise xor operation. Alice has a winning strategy in the normal play of Nim if and only if nim-sum (\Phi)>0 . Moreover, Alice has a winning strategy in the misère play of Nim if and only if nim-sum (\Phi)>0 and there is at least one heap with more than one object, or nim-sum (\Phi)=0 and all non-empty heaps have exactly one object. The winning strategies in both variants is to finish every move with

Read the complete text