Abstract
LetG = (V, E) be a finite graph. The setL of labeled vertices is initially empty. Two players A and B move alternately (A first), by choosing an unlabled vertexu ε ∈V\L; thenu itself and all vertices on shortest paths betweenu and any vertex ofL are adjoined toL. WhenL =V, the game is over. Innormal play, the first player unable to move loses and his opponent wins. The outcome is reversed formisère play. We resolve the game by determining its winning strategies for the following cases: trees in normal play; cycles in normal and misère play; and complete graphsK m with rays all of lengthn, in normal play.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berlekamp E R, Conway J H and Guy R K (1982) Winning Ways, Academic Press, London
Harary F, Achievement and Avoidance Games (book in preparation)
Úlehla J (1980) A complete analysis of Von Neumann's Hackendot, Int. J. Game Theory 9, 107–113
Author information
Authors and Affiliations
Additional information
Partial support by Canadian Research Grants 69-0695 and A-4792 during visits at the University of Calgary and Simon Fraser University is gratefully acknowledged.
Rights and permissions
About this article
Cite this article
Fraenkel, A.S., Harary, F. Geodetic contraction games on graphs. Int J Game Theory 18, 327–338 (1989). https://doi.org/10.1007/BF01254296
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01254296