Geodetic Achievement and Avoidance Games For Graphs

Abstract

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 v ₁ of G. The second player B then selects v ₂ ≠ v ₁ and determines the geodetic closure (S ₂) for S ₂ = {v ₁ , v ₂ }. If (S ₂) = V, then the second player wins the achievement game, but loses the avoidance game. If (S ₂) = V, then A picks v ₃ ∉ S ₂ and determines (S ₃) for S ₃ = {v ₁ , v ₂ , v ₃ }. In general, A and B alternatively select a new vertex in this manner. The first player who selects a vertex v _k such that (S _k) = 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.