Geodetic achievement and avoidance games for graphs

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

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

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 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.

Original languageEnglish
Pages (from-to)389-397
Number of pages9
JournalQuaestiones Mathematicae
Volume26
Issue number4
DOIs
Publication statusPublished - Dec 2003
Externally publishedYes

Keywords

  • Achievement Game
  • Avoidance Game
  • Geodetic Closure
  • Geodetic Cover

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Geodetic achievement and avoidance games for graphs'. Together they form a unique fingerprint.

Cite this