Making Graphs Solvable in Peg Solitaire

Abstract

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.

Introduction

References

[1] R. A. Beeler and A. D. Gray, Extremal results for peg solitaire on graphs, Bull. Inst. Combin. Appl. 77 (2016), 30–42. [2] R. A. Beeler, H. Green and R. T. Harper, Peg solitaire on caterpillars, Integers 17 (2017), G1. [3]R. A. Beeler and D. P. Hoilman, Peg solitaire on graphs,Discrete Math. 311 (20) (2011),2198–2202. [3] R. A. Beeler and D. P. Hoilman, Peg solitaire on the windmill and the double star graphs, Australas. J. Combin. 52 (2012), 127–134. [4] R. A. Beeler and T. K. Rodriguez, Fool’s solitaire on graphs, Involve 5 (4) (2012), 473–480. [5] G. I. Bell, Solving triangular peg solitaire, J. Integer Seq. 11 (2008), Article 08.4.8

Copyright

Copyright © 2022 Saranya M, Naveen L. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.