کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418191 | 681617 | 2015 | 7 صفحه PDF | دانلود رایگان |
The Clobber game was introduced by Albert et al. in 2002, then its solitaire version that we are interested in was presented by Demaine et al. in 2004. Solitaire Clobber is played on a graph GG, by placing a stone, black or white, on each vertex of the graph. A move consists in picking up a stone and clobbering another one of opposite color located on an adjacent vertex; the clobbered stone is removed from the graph and is replaced by the picked one. The goal is to minimize the number of stones remaining when no further move is possible. We investigate a more restrictive question related to the color and the location of the remaining stones. A graph is strongly 11-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. This question was studied by Dorbec et al. (2008) for multiple Cartesian product of cliques (Hamming graphs). In this paper, we generalize this result by proving that if we have two strongly 11-reducible connected graphs GG and HH (both graphs with at least seven vertices) then G□HG□H is strongly 11-reducible.
Journal: Discrete Applied Mathematics - Volume 182, 19 February 2015, Pages 84–90