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.

Mathematics Subject
Classification (2000): 05C99, 91A05, 91A43.

Key words: Achievement game, avoidance game,
geodetic cover, geodetic closure.


Quaestiones Mathematicae 26(2003), 389–397