Directed Switching Games II. The arborescence Game

Y.O. Hamidoune, M. Las Vergnas

IBP-EC 1995/14: Rapport de Recherche EC / EC research reports
9 pages - Janvier/January 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Directed Switching Games II. The arborescence Game

Résumé : Dans le jeu de l'Arborescence, deux joueurs, Blanc et Noir, jouent alternativement les arêtes d'un graphe non orienté avec un sommet distingué xo . Un coup de Noir consiste à enlever une arête non encore joué. Un coup de Blanc consiste à orienter une arête non jouée. Blanc gagne si et seulement si il forme une arborescence de racine xo .
Nous caractérisons les positions gagnantes du jeu de l'Arborescence dans le cas où le graphe est réunion de deux arbres couvrants arête-disjoints. La stratégie générale en découle.

Abstract : In the arborescence Game, two players, Black and White, play alternately edges of an undirected graph with a specified vertex xo . A move of Black consists of deleting an unplayed edge. A move of White consists of directing an unplayed edge. White wins if he forms a spanning arborescence rooted at xo and loses otherwise.
We characterize winning positions for the Arborescence Game in the case when the graph is a disjoint union of two spanning trees. The general strategy follows

Publications internes EC 1995 / EC research reports 1995