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 x y z form a 3-vertex path and x and y each has 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 ( G ¿ K k ) when k ¿ 3 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 ( G ¿ H ) ¿ F ( G ) F ( H ) . |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.disc.2014.10.022 | Discrete Mathematics |
Keywords | Field | DocType |
Peg solitaire,Fool’s solitaire,Games on graphs | Discrete mathematics,Graph,Joins,Combinatorics,Solitaire Cryptographic Algorithm,Vertex (geometry),Cartesian product,Mathematics | Journal |
Volume | Issue | ISSN |
338 | 3 | 0012-365X |
Citations | PageRank | References |
1 | 0.43 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sarah Loeb | 1 | 4 | 2.52 |
Jennifer Wise | 2 | 3 | 1.23 |