GEODETIC GAMES FOR GRAPHS
Fred Buckley, Frank Harary · Quaestiones Mathematicae · 1985
Let S be a subset of the vertex set V(G) of a nontrivial connected graph G. The geodetic closure (S) of S is the set of all vertices on geodesics between two vertices in S. The first player A chooses a vertex v1 of G. The second player B then picks v2 ≠ v1 and forms the geodetic closure (S2) = ({v1, v2}). Now A selects v3 ε V—S2 and forms (S3) = ({v1, v2, v3}), etc. The player who first selects a vertex vn such that (Sn) = V wins the achievement game, but loses the avoidance game. These geodetic achievement and avoidance games are solved for several families of graphs by determining which player is the winner.