Fool's solitaire on joins and Cartesian products of graphs

DOI10.1016/J.DISC.2014.10.022MaRDI QIDQ482200zbMATH OpenOpenAlexFDO

Authors Sarah Loeb, Jennifer I. Wise

Publication date 19 December 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.7105

zbMATH Keywords

games on graphspeg solitairefool's solitaire

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph operations (line graphs, products, etc.) (05C76) Games involving graphs (91A43) Combinatorial games (91A46)

Abstract: Peg solitaire is a game generalized to connected graphs by Beeler and Hoilman. In the game pegs are placed on all but one vertex. If $xyz$ form a 3-vertex path and $x$ and $y$ each have a peg but $z$ does not, then we can remove the pegs at $x$ and $y$ and place a peg at $z$. By analogy with the moves in the original game, this is called a jump. The goal of the peg solitaire game on graphs is to find jumps that reduce the number of pegs on the graph to 1. Beeler and Rodriguez proposed a variant where we instead want to maximize the number of pegs remaining when no more jumps can be made. Maximizing over all initial locations of a single hole, the maximum number of pegs left on a graph $G$ when no jumps remain is the fool's solitaire number $F(G)$. We determine the fool's solitaire number for the join of any graphs $G$ and $H$. For the cartesian product, we determine $F(GBox{K}_k)$ when $kge3$ and $G$ is connected and show why our argument fails when $k=2$. Finally, we give conditions on graphs $G$ and $H$ that imply $F(GBoxH)geF(G)F(H)$.

Recommendations

• Fool's solitaire on graphs
• Solitaire clobber played on Cartesian product of graphs
• Peg solitaire on Cartesian products of graphs
• Strong reducibility of solitaire clobber played on Cartesian product of graphs
• Solitaire Clobber on circulant graphs
• The solitaire clobber game and correducibility of graphs
• Path-Stick Solitaire on Graphs
• Solitaire Clobber played on Hamming graphs
• scientific article; zbMATH DE number 739124

Cites work

• scientific article; zbMATH DE number 6509361 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Diagonal peg solitaire
• Fool's solitaire on graphs
• Peg solitaire on graphs
• Peg solitaire on graphs with seven vertices or less

Cited in

(12)

• Peg solitaire on Cartesian products of graphs
• Peg solitaire on graphs with jumping and merging allowed
• Fagan's Construction, Strange Roots, and Tchoukaillon Solitaire
• Peg solitaire in three colors on graphs
• Reversible peg solitaire on graphs
• Merging peg solitaire on graphs
• Peg solitaire game on Sierpinski graphs
• Peg solitaire on graphs -- a survey
• Fool's solitaire on graphs
• Extremal results for Peg solitaire on graphs
• Examples of edge critical graphs in peg solitaire
• Making graphs solvable in peg solitaire

This page was built for publication: Fool's solitaire on joins and Cartesian products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482200)