Impartial geodetic building games on graphs

Bret J. Benesh (), Dana C. Ernst (), Marie Meyer (), Sarah K. Salmon () and Nándor Sieben ()
Additional contact information
Bret J. Benesh: Saint John’s University
Dana C. Ernst: Northern Arizona University
Marie Meyer: Lewis University
Sarah K. Salmon: University of Colorado Boulder Campus Box 395
Nándor Sieben: Northern Arizona University

International Journal of Game Theory, 2024, vol. 53, issue 4, No 12, 1335-1368

Abstract: Abstract 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.

Keywords: Impartial hypergraph game; Geodetic convex hull; 91A46; 52A01; 52B40 (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-024-00916-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:53:y:2024:i:4:d:10.1007_s00182-024-00916-0

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-024-00916-0

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().