Name
Abstract | ||
|---|---|---|
Solitaire Clobber is a one-player combinatorial game on graphs. Each vertex of a graph G starts with a black or a white stone. A stone on one vertex can clobber an adjacent stone of the opposite color, removing it and taking its place. The goal is to minimize the number of stones remaining when no further move is possible. An initial configuration is k-reducible if it can be reduced to k stones. A graph is strongly 1-reducible if, for any vertex v, any initial configuration that is not monochromatic outside v can be reduced to one stone, on v, of either color. Every such graph has a Hamiltonian path ending at v. For the path Pn, we prove that the rth distance power Pnr is strongly 1-reducible when r≥3 but not when r=2 (Pn2 is 2-reducible). As a consequence, circulant graphs containing edges of lengths 1, 2, and 3 are strongly 1-reducible; we show also that those containing Cn2 are 1-reducible. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.disc.2014.04.006 | Discrete Mathematics |
Keywords | Field | DocType |
Graph theory,Combinatorial games,Solitaire clobber | Graph theory,Discrete mathematics,Combinatorial game theory,Combinatorics,Circulant graph,Monochromatic color,Vertex (geometry),Hamiltonian path,Neighbourhood (graph theory),Circulant matrix,Mathematics | Journal |
Volume | ISSN | Citations |
329 | 0012-365X | 1 |
PageRank | References | Authors |
0.41 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Telma Pará | 1 | 7 | 2.29 |
| Simone Dantas | 2 | 119 | 24.99 |
| Sylvain Gravier | 3 | 486 | 59.01 |