کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647190 | 1632413 | 2014 | 9 صفحه PDF | دانلود رایگان |

Solitaire Clobber is a one-player combinatorial game on graphs. Each vertex of a graph GG 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 kk-reducible if it can be reduced to kk stones. A graph is strongly 1-reducible if, for any vertex vv, any initial configuration that is not monochromatic outside vv can be reduced to one stone, on vv, of either color. Every such graph has a Hamiltonian path ending at vv. For the path PnPn, we prove that the rrth distance power Pnr is strongly 1-reducible when r≥3r≥3 but not when r=2r=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.
Journal: Discrete Mathematics - Volume 329, 28 August 2014, Pages 33–41