# Quaestiones Mathematicae

Open Access  Subscription or Fee Access

### Geodetic achievement and avoidance games for graphs

Teresa W. Haynes, Michael A. Henning, Charlotte Tiller

#### Abstract

Let G =
(V,E) be a
nontrivial connected graph. For a subset SV, 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 v3S2 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 vksuch 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–397

EMAIL FULL TEXT