A constructive graph-theoretic solution of the Shannon switching game

Publisher Website
Google Scholar
Abstract
A simple graph-theoretic solution to the Shannon two-person switching game is given. The solution is constructive in that algorithms have been formulated to determine if a game played on any given graph is a short, cut, or a neutral game. The proof makes use of a result due to Kishi and Kajitani, who showed that the edges of any linear graphGcan be decomposed into a partition containing three blocks. From this partition one constructs three graphs that form a principal partition denoted by the ordered triple (D2, G2, H2). It is proved that the game is a short (cut) [neutral] game if and only if a distinguished edge e belongs toG_{2}(H_{2}) [D_{2}]. Strategies for playing each game are given. Finally, duality theory is used to prove that a global strategy exists for a cut game as well as for a short game, where by a global strategy with respect to a short game is meant that the short player can win with respect to any edge spanned by the pair of cospanning trees without knowing which of these edges is the distinguished edge with respect to the game being played.

This publication has 3 references indexed in Scilit: