Geodetic Achievement and Avoidance Games for Graphs
Document Type
Article
Publication Date
1-1-2003
Description
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 (S 2) for S 2 = {v 1 , v 2 }. If (S 2) = V, then the second player wins the achievement game, but loses the avoidance game. If (S 2) = V, then A picks v 3 ∉ S 2 and determines (S 3) for S 3 = {v 1 , v 2 , v 3 }. 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.
Citation Information
Haynes, Teresa W.; Henning, Michael A.; and Tiller, Charlotte. 2003. Geodetic Achievement and Avoidance Games for Graphs. Quaestiones Mathematicae. Vol.26(4). 389-397. https://doi.org/10.2989/16073600309486069 ISSN: 1607-3606