Peg solitaire on graphs with jumping and merging allowed (Q2109085)

For more than three centuries mathematicians are familiar with the Peg solitaire game which is a one-player table game. At the beginning of the last decade, this problem was generalized to graphs. In this game, pegs are placed in every hole but one and the player jumps over pegs along rows or columns to remove them. The aim of the player is to leave only one peg. The authors here consider a new variant of peg solitaire on graphs in which pegs can be removed either by jumping them or by merging them. For this variant, they show that several classes of graphs are solvable. By solvability they mean the following: the game begins with a hole in one vertex and pegs in all others. After a sequence of legal moves, one arrives at a terminal state where no further moves are possible. So the player's aim is to minimize the number of pegs in the terminal state. Starting with a single hole, if one arrives at a terminal state consisting of a single peg, then the graph is said to be solvable. Stimulated by this they seek to consider a variant of peg solitaire in which the player is allowed to use both the traditional jump move as well as the merge move. The aim is to prove the solvability of certain graph families in the new ``jump + merge'' variant. Note that any graph that is solvable in the jump-only variant or the merge-only variant will still be solvable in the jump+merge variant. For instance, the path on \(n\) vertices is shown to be solvable using only merge moves in. The authors establish here that there are graphs that are not solvable in either variant and that are solvable when both jumping and merging are allowed. These graphs include stars, caterpillars, trees of diameter 4, trees of diameter 5, and articulated caterpillars. The authors also give several open problems related to this for other researchers working in this area.