Trail Trap: a variant of Partizan Edge Geography
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911082542530560 |
|---|---|
| author | Buchanan, Calum Carr, MacKenzie Clifton, Alexander Hartke, Stephen G. Iršič, Vesna Sieger, Nicholas Whitman, Rebecca |
| author_facet | Buchanan, Calum Carr, MacKenzie Clifton, Alexander Hartke, Stephen G. Iršič, Vesna Sieger, Nicholas Whitman, Rebecca |
| contents | We study a two-player game played on undirected graphs called {\sc Trail Trap}, which is a variant of a game known as {\sc Partizan Edge Geography}. One player starts by choosing any edge and moving a token from one endpoint to the other; the other player then chooses a different edge and does the same. Alternating turns, each player moves their token along an unused edge from its current vertex to an adjacent vertex, until one player cannot move and loses. We present an algorithm to determine which player has a winning strategy when the graph is a tree and partially characterize the trees on which a given player wins. Additionally, we show that it is NP-hard to determine if Player~2 has a winning strategy on {\sc Trail Trap} from the starting position, even for connected bipartite planar graphs with maximum degree $4$. We determine which player has a winning strategy for certain subclasses of complete bipartite graphs and grid graphs, and we propose several open problems for further study. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05195 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Trail Trap: a variant of Partizan Edge Geography Buchanan, Calum Carr, MacKenzie Clifton, Alexander Hartke, Stephen G. Iršič, Vesna Sieger, Nicholas Whitman, Rebecca Combinatorics Discrete Mathematics 91A43 (05C57, 68Q17) We study a two-player game played on undirected graphs called {\sc Trail Trap}, which is a variant of a game known as {\sc Partizan Edge Geography}. One player starts by choosing any edge and moving a token from one endpoint to the other; the other player then chooses a different edge and does the same. Alternating turns, each player moves their token along an unused edge from its current vertex to an adjacent vertex, until one player cannot move and loses. We present an algorithm to determine which player has a winning strategy when the graph is a tree and partially characterize the trees on which a given player wins. Additionally, we show that it is NP-hard to determine if Player~2 has a winning strategy on {\sc Trail Trap} from the starting position, even for connected bipartite planar graphs with maximum degree $4$. We determine which player has a winning strategy for certain subclasses of complete bipartite graphs and grid graphs, and we propose several open problems for further study. |
| title | Trail Trap: a variant of Partizan Edge Geography |
| topic | Combinatorics Discrete Mathematics 91A43 (05C57, 68Q17) |
| url | https://arxiv.org/abs/2405.05195 |