A New Dominating Set Game on Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908619419680768 |
|---|---|
| author | Fiscus, Sean Hurlbert, Glenn Myzelev, Eric Pence, Travis |
| author_facet | Fiscus, Sean Hurlbert, Glenn Myzelev, Eric Pence, Travis |
| contents | We introduce a new two-player game on graphs, in which players alternate choosing vertices until the set of chosen vertices forms a dominating set. The last player to choose a vertex is the winner. The game fits into the scheme of several other known games on graphs. We characterize the paths and cycles for which the first player has the winning strategy. We also create tools for combining graphs in various ways (via graph powers, Cartesian products, graph joins, and other methods) for building a variety of graphs whose games are won by the second player, including cubes, multidimensional grids with an odd number of vertices, most multidimensional toroidal grids, various trees such as specialized caterpillars, the Petersen graph, and others. Finally, we extend the game to groups and show that the second player wins the game on abelian groups of even order with canonical generating set, among others. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03448 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A New Dominating Set Game on Graphs Fiscus, Sean Hurlbert, Glenn Myzelev, Eric Pence, Travis Combinatorics 91A43, 05C57 We introduce a new two-player game on graphs, in which players alternate choosing vertices until the set of chosen vertices forms a dominating set. The last player to choose a vertex is the winner. The game fits into the scheme of several other known games on graphs. We characterize the paths and cycles for which the first player has the winning strategy. We also create tools for combining graphs in various ways (via graph powers, Cartesian products, graph joins, and other methods) for building a variety of graphs whose games are won by the second player, including cubes, multidimensional grids with an odd number of vertices, most multidimensional toroidal grids, various trees such as specialized caterpillars, the Petersen graph, and others. Finally, we extend the game to groups and show that the second player wins the game on abelian groups of even order with canonical generating set, among others. |
| title | A New Dominating Set Game on Graphs |
| topic | Combinatorics 91A43, 05C57 |
| url | https://arxiv.org/abs/2504.03448 |