Permutation sorting and a game on graphs

Abstract

We introduce a game on graphs. By a theorem of Zermelo, each instance of the game on a finite graph is determined. While the general decision problem on which player has a winning strategy in a given instance of the game is unsolved, we solve the decision problem for a specific class of finite graphs. This result is then applied to a permutation sorting game to prove the optimality of a proportional bound under which TWO has a winning strategy.

14 pages

Cited by in corpus (2)

• The Sortability of Graphs and Matrices under Context Directed Swaps
• Classifying Permutations under Context-Directed Swaps and the \textbf{cds} game