Making graphs solvable in peg solitaire

Jan-Hendrik de Wiljes, Martin Kreh

Abstract


In 2011, Beeler and Hoilman generalized the game of peg solitaire to arbitrary connected graphs. Since then peg solitaire has been considered on quite a few classes of graphs. Beeler and Gray introduced the natural idea of adding edges to make an unsolvable graph solvable. Recently, the graph invariant ms(G), which is the minimal number of additional edges needed to make G solvable, has been introduced and investigated on banana trees by the authors. In this article, we determine ms(G) for several families of unsolvable graphs. Furthermore, we provide some general results for this number of Hamiltonian graphs and graphs obtained via binary graph operations.


Keywords


peg solitaire, windmill, double star

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.3

References

R.A. Beeler and A.D. Gray, Extremal results for peg solitaire on graphs, Bull. Inst. Combin. Appl. 77 (2016), 30–42.

R.A. Beeler, H. Green, and R.T. Harper, Peg solitaire on caterpillars, Integers 17 (2017), G1.

R.A. Beeler and D.P. Hoilman, Peg solitaire on graphs, Discrete Math. 311(20) (2011), 2198–2202.

R.A. Beeler and D.P. Hoilman, Peg solitaire on the windmill and the double star graphs, Australas. J. Combin. 52 (2012), 127–134.

R.A. Beeler and T.K. Rodriguez, Fool’s solitaire on graphs, Involve 5(4) (2012), 473–480.

R.A. Beeler and C.A. Walvoort, Peg solitaire on trees with diameter four, Australas. J. Combin. 63(3) (2015), 321–332.

G.I. Bell, Solving triangular peg solitaire, J. Integer Seq. 11 (2008), Article 08.4.8.

J.H. de Wiljes and M. Kreh, Peg solitaire on banana trees, Bull. Inst. Combin. Appl. 90 (2020), 63–86.

J. Engbers and C. Stocker, Reversible peg solitaire on graphs, Discrete Math. 338(11) (2015), 2014–2019.

M. Kreh and J.H. de Wiljes, Peg solitaire on Cartesian products of graphs, Graphs Comb. 37(3) (2021), 907–917.

S. Loeb and J. Wise, Fool’s solitaire on joins and Cartesian products of graphs, Discrete Math. 338(3) (2015), 66–71.

P. Manuel, Revisiting path-type covering and partitioning problems, hal-01849313 (2009)


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats