Explorations of the Shannon Switching Game

The Shannon switching game is a combinatorial game that is traditionally played by one robber and one cop on a graph with a specified starting and ending vertex. The robber and cop alternate turns and either player can go first. The robber attempts to trace a path from the starting vertex to the ending vertex by tracing one unmarked edge per turn. The cop attempts to prevent a path from the starting vertex to the ending vertex by deleting one unmarked edge per turn. The robber wins the game if the robber creates a path from the starting vertex to the ending vertex. The cop wins if all edges have been traced or deleted, but the robber was unable to create a path from the starting vertex to the ending vertex. This game has applications in computer science and social network theory. This project explores variations in the original Shannon switching game. Kimberly Wood researched a variation in the game involving multiple cops and one robber on complete graphs and was able to find results for which graphs the multiple cops or one robber can win or lose. We further define the bounds of Wood’s research on complete graphs with multiple cops and one robber. Then, we conclude by looking at different ways to sum two games and seeing who wins on sums with multiple cops and one robber or multiple robbers and one cop