Quaestiones Mathematicae

Log in or Register to get access to full text downloads.

Remember me or Register

DOWNLOAD FULL TEXT Open Access  DOWNLOAD FULL TEXT Subscription or Fee Access

Geodetic achievement and avoidance games for graphs

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


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)
two vertices of S. We study the
geodetic achievement and avoidance games defined by Buckley and Harary
(Geodetic games for graphs, Quaestiones
. 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
AJOL African Journals Online