Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2506.21281 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909660680814592 |
|---|---|
| author | Graafsma, Denise Manthey, Bodo Skopalik, Alexander |
| author_facet | Graafsma, Denise Manthey, Bodo Skopalik, Alexander |
| contents | Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_21281 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Playing Snake on a Graph Graafsma, Denise Manthey, Bodo Skopalik, Alexander Discrete Mathematics Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight. |
| title | Playing Snake on a Graph |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2506.21281 |