## 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_{1} of G. The second player B then selects v_{2} ≠ v_{1} 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 language | English |
---|---|

Pages (from-to) | 389-397 |

Number of pages | 9 |

Journal | Quaestiones Mathematicae |

Volume | 26 |

Issue number | 4 |

DOIs | |

Publication status | Published - Dec 2003 |

Externally published | Yes |

## Keywords

- Achievement Game
- Avoidance Game
- Geodetic Closure
- Geodetic Cover

## ASJC Scopus subject areas

- Mathematics (miscellaneous)