# New results about impartial solitaire clobber

Eric Duchêne; Sylvain Gravier; Julien Moncel

RAIRO - Operations Research (2009)

- Volume: 43, Issue: 4, page 463-482
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topDuchêne, Eric, Gravier, Sylvain, and Moncel, Julien. "New results about impartial solitaire clobber." RAIRO - Operations Research 43.4 (2009): 463-482. <http://eudml.org/doc/250552>.

@article{Duchêne2009,

abstract = {
Impartial Solitaire Clobber is a one-player version of the combinatorial game Clobber, introduced by Albert et al. in 2002.
The initial configuration of Impartial Solitaire Clobber is a graph, such that there is a stone placed on each of its vertex,
each stone being black or white. A move of the game consists in picking a stone, and clobbering an adjacent stone of the opposite color.
By clobbering we mean that the clobbered stone is removed from the graph, and replaced by the clobbering one. The aim is to make a sequence
of moves leaving the minimum number of stones on the graph; this number is called the reducibility value of the configuration.
As any one-player game, Solitaire Clobber is essentially an optimization problem,
whose resolution may give bounds on the two-player version of the game. As an optimization problem, Solitaire Clobber can be considered as a constrained version of the underlying optimization problem related to Hamiltonian path. This enables to show that Solitaire Clobber is NP-hard. Solitaire Clobber was already studied in various graph structures, including paths, cycles, trees, and Hamming graphs. In this paper we investigate the problem in complete multipartite graphs. In particular, we give a linear-time algorithm computing the reducibility value of any configuration in complete multipartite graphs. We also address some extremal questions related to Solitaire Clobber in general graphs.
},

author = {Duchêne, Eric, Gravier, Sylvain, Moncel, Julien},

journal = {RAIRO - Operations Research},

keywords = {Combinatorial games; games invoking graphs; extremal problem; solitaire clobber.; combinatorial games; solitaire clobber},

language = {eng},

month = {10},

number = {4},

pages = {463-482},

publisher = {EDP Sciences},

title = {New results about impartial solitaire clobber},

url = {http://eudml.org/doc/250552},

volume = {43},

year = {2009},

}

TY - JOUR

AU - Duchêne, Eric

AU - Gravier, Sylvain

AU - Moncel, Julien

TI - New results about impartial solitaire clobber

JO - RAIRO - Operations Research

DA - 2009/10//

PB - EDP Sciences

VL - 43

IS - 4

SP - 463

EP - 482

AB -
Impartial Solitaire Clobber is a one-player version of the combinatorial game Clobber, introduced by Albert et al. in 2002.
The initial configuration of Impartial Solitaire Clobber is a graph, such that there is a stone placed on each of its vertex,
each stone being black or white. A move of the game consists in picking a stone, and clobbering an adjacent stone of the opposite color.
By clobbering we mean that the clobbered stone is removed from the graph, and replaced by the clobbering one. The aim is to make a sequence
of moves leaving the minimum number of stones on the graph; this number is called the reducibility value of the configuration.
As any one-player game, Solitaire Clobber is essentially an optimization problem,
whose resolution may give bounds on the two-player version of the game. As an optimization problem, Solitaire Clobber can be considered as a constrained version of the underlying optimization problem related to Hamiltonian path. This enables to show that Solitaire Clobber is NP-hard. Solitaire Clobber was already studied in various graph structures, including paths, cycles, trees, and Hamming graphs. In this paper we investigate the problem in complete multipartite graphs. In particular, we give a linear-time algorithm computing the reducibility value of any configuration in complete multipartite graphs. We also address some extremal questions related to Solitaire Clobber in general graphs.

LA - eng

KW - Combinatorial games; games invoking graphs; extremal problem; solitaire clobber.; combinatorial games; solitaire clobber

UR - http://eudml.org/doc/250552

ER -

## References

top- M.H. Albert, J.P. Grossman, R.J. Nowakowski and D. Wolfe, An introduction to Clobber. INTEGERS5 (2005). Zbl1139.91013
- L. Beaudou, E. Duchêne and S. Gravier, A survey about Solitaire Clobber (submitted). Zbl06490898
- V.D. Blondel, C. de Kerchove, J.M. Hendrickx and R. Jungers, Solitaire Clobber as an optimization problem on words. INTEGERS7 (2008). Zbl1233.91052
- B. Bollobás, Random graphs. Cambridge University Press (2001). Zbl0979.05003
- E.D. Demaine, M.L. Demaine and R. Fleischer, Solitaire Clobber. Theor. Comput. Sci.313 (2004) 325–338.
- P. Dorbec, E. Duchêne and S. Gravier, Solitaire Clobber played on Hamming graphs. Integers, J. Comb. No. Theory7 (2008). Zbl1233.91054
- A. Itai, C.H. Papadimitriou and J.L. Szwarcfiter, Hamilton paths in grid graphs. SIAM J. Comput.11 (1982) 676–686. Zbl0506.05043
- I. Peterson, Getting clobbered, Science News161 (2002), http://www.sciencenews.org/articles/20020427/mathtrek.asp.
- M. Ruszinkó, private communication.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.