Impartial geodetic building games on graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910651703623680 |
|---|---|
| author | Benesh, Bret J. Ernst, Dana C. Meyer, Marie Salmon, Sarah Sieben, Nandor |
| author_facet | Benesh, Bret J. Ernst, Dana C. Meyer, Marie Salmon, Sarah Sieben, Nandor |
| contents | A subset of the vertex set of a graph is geodetically convex if it contains every vertex on any shortest path between two elements of the set. The convex hull of a set of vertices is the smallest convex set containing the set. We study variations of two games introduced by Buckley and Harary, where two players take turns selecting previously-unselected vertices of a graph until the convex hull of the jointly-selected vertices becomes too large. The last player to move is the winner. The achievement game ends when the convex hull contains every vertex. In the avoidance game, the convex hull is not allowed to contain every vertex. We determine the nim-value of these games for several graph families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_07095 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Impartial geodetic building games on graphs Benesh, Bret J. Ernst, Dana C. Meyer, Marie Salmon, Sarah Sieben, Nandor Combinatorics 91A46, 52A01, 52B40 A subset of the vertex set of a graph is geodetically convex if it contains every vertex on any shortest path between two elements of the set. The convex hull of a set of vertices is the smallest convex set containing the set. We study variations of two games introduced by Buckley and Harary, where two players take turns selecting previously-unselected vertices of a graph until the convex hull of the jointly-selected vertices becomes too large. The last player to move is the winner. The achievement game ends when the convex hull contains every vertex. In the avoidance game, the convex hull is not allowed to contain every vertex. We determine the nim-value of these games for several graph families. |
| title | Impartial geodetic building games on graphs |
| topic | Combinatorics 91A46, 52A01, 52B40 |
| url | https://arxiv.org/abs/2307.07095 |