Geodetic achievement and avoidance games for graphs

Let G = (V,E) be a nontrivial connected graph. For a subset S ⊆ V, the geodesic closure (S) of S is the set of all vertices on geodesics (shortest paths) between two vertices of S. We study the geodetic achievement and avoidance games defined by Buckley and Harary (Geodetic games for graphs, Quaestiones Math. 8 (1986), 321–334) as follows. The first player A chooses a vertex v1 of G. The second player B then selects v2≠ v1 and determines the geodetic closure (S2) for S2 = {v1, v2}. If (S2) = V, then the second player wins the achievement game, but loses the avoidance game. If (S2) ≠ V, then A picks v3 ∉ S2 and determines (S3) for S3 = {v1, v2, v3}. In general, A and B alternatively select a new vertex in this manner. The first player who selects a vertex vk such that (Sk) = V wins the achievement game; in the avoidance game he is the loser. We solve these games for several families of graphs, including trees and complete multipartite graphs, by determining which player is the winner. Mathematics Subject Classification (2000): 05C99, 91A05, 91A43. Key words: Achievement game, avoidance game, geodetic cover, geodetic closure. Quaestiones Mathematicae 26(2003), 389–39