Directed switching games. II: The arborescence game. (English) Zbl 0873.90138
Summary: [For part I see the authors, C. R. Acad. Sci., Paris Sér. I 298, 497-499 (1984; Zbl 0559.90099).]
The Arborescence Game is a two-player game on a connected undirected graph with a distinguished vertex \(x_0\). The two players, say Black and White, pick alternately an unplayed edge. A move of Black consists of deleting the chosen edge. A move of White consists of directing the chosen edge. White wins if and only if he forms a spanning arborescence rooted at \(x_0\). We characterize winning positions of the Arborescence Game in the case when the graph is a disjoint union of two spanning trees. General strategies follow.
The Arborescence Game is a two-player game on a connected undirected graph with a distinguished vertex \(x_0\). The two players, say Black and White, pick alternately an unplayed edge. A move of Black consists of deleting the chosen edge. A move of White consists of directing the chosen edge. White wins if and only if he forms a spanning arborescence rooted at \(x_0\). We characterize winning positions of the Arborescence Game in the case when the graph is a disjoint union of two spanning trees. General strategies follow.
MSC:
| 91A43 | Games involving graphs |
Keywords:
arborescence game; connected undirected graph; winning positions; disjoint union of two spanning treesCitations:
Zbl 0559.90099References:
| [1] | Hamidoune, Y. O.; Vergnas, M. Las, Directed Switching Games on graphs and matroids, J. Combin. Theory Ser. B, 40, 237-269 (1986) · Zbl 0589.90109 |
| [2] | Lehman, A., A solution to the Shannon Switching Game, J. Soc. Indust. Appl. Math., 12, 687-725 (1964) · Zbl 0137.38704 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
