#### Document Type

Article

#### Language

eng

#### Format of Original

6 p.

#### Publication Date

11-2015

#### Publisher

Elsevier

#### Source Publication

Discrete Mathematics

#### Source ISSN

0012-365X

#### Original Item ID

doi: 10.1016/j.disc.2015.05.012

#### Abstract

The game of peg solitaire on graphs was introduced by Beeler and Hoilman in 2011. In this game, pegs are initially placed on all but one vertex of a graph **G**. If **xyz** forms a path in **G** and there are pegs on vertices **x** and **y** but not **z**, then a *jump* places a peg on **z** and removes the pegs from** x** and **y**. A graph is called solvable if, for some configuration of pegs occupying all but one vertex, some sequence of jumps leaves a single peg. We study the game of *reversible peg solitaire*, where there are again initially pegs on all but one vertex, but now both jumps and unjumps (the reversal of a jump) are allowed. We show that in this game all non-star graphs that contain a vertex of degree at least three are solvable, that cycles and paths on **n** vertices, where **n** is divisible by 2 or 3, are solvable, and that all other graphs are not solvable. We also classify the possible starting hole and ending peg positions for solvable graphs.

## Comments

Accepted version.

Discrete Mathematics, Vol. 338, No. 11 (November 2015): 2014-2019. DOI. © Elsevier 2015. Used with permission.