Topological Network-Control Games Played on Graphs

We study topological network-control games. These games belong to the class of scoring games in combinatorial game theory. In a topological network-control game, given a graph** G, two players move alternately on G. During each move, a player selects an unclaimed vertex along with its unclaimed neighbors within the distance of **t. The players should satisfy the topological condition that the set of all claimed vertices at each move stays connected. The objective is to decide which player can claim more vertices at the end of the game. We focus on deciding topological network-control games on unions of path graphs and unions of cycles. We fully solve our games by finding the winners and computing winning strategies on these graphs. These findings bring new insights into our understanding of prototypical examples of scoring games, – topological network-control games, and contribute to the development of combinatorial game theory.

Recommended citation: Liang, Z., Khoussainov, B., Yang, H. (2025). Topological Network-Control Games Played on Graphs. In: Chen, Y., Gao, X., Sun, X., Zhang, A. (eds) Computing and Combinatorics. COCOON 2024. Lecture Notes in Computer Science, vol 15162. Springer, Singapore. https://doi.org/10.1007/978-981-96-1093-8_2
Download Paper