Playing Snake on a Graph
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_ | 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 |