Peg solitaire on the windmill and the double star graphs.

Abstract

In a recent work by Beeler and Hoilman, the game of peg solitaire is generalized to arbitrary boards. These boards are treated as graphs in the combinatorial sense. In this paper, we extend this study by considering the windmill and the double star. Simple necessary and sufficient conditions are given for the solvability of each graph. We also discuss an open problem concerning the range of values for which a graph has a terminal state with k pegs.