We study the following combinatorial game played by two players, Alice and Bob. Given a connected graphG with nonnegative weights assigned to its vertices, the players alternately take one vertex ofG in each turn. The first turn is Alice’s. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph ofG induced by the taken vertices is connected during the whole game, (R) the subgraph ofG induced by the remaining vertices is connected during the whole game. We show that under all the three combinations of rules (T) and (R), for everyε> 0 and for everyk ≥ 1 there is ak-connected graphG for which Bob has a strategy to obtain (1 − ε) of the total weight of the vertices. This contrasts with the game played on a cycle, where Alice is known to have a strategy to obtain 4/9 of the total weight.

We show that the problem of deciding whether Alice has a winning strategy (i.e., a strategy to obtain more than half of the total weight) is PSPACE-complete if condition (R) or both conditions (T) and (R) are required. We also consider a variation of the game where the first player who violates condition (T) or (R) loses the game. We show that deciding who has the winning strategy is PSPACE-complete.

Unable to display preview. Download preview PDF.

Authors and Affiliations

1. Department of Applied Mathematics, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00, Praha 1, Czech Republic

   Josef Cibulka & Rudolf Stolař

2. Department of Applied Mathematics and, Institute for Theoretical Computer Science, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00, Praha 1, Czech Republic

   Jan Kynčl, Viola Mészáros & Pavel Valtr

3. Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, 6720, Szeged, Hungary

   Viola Mészáros

Editors and Affiliations

1. Charles University, Malostranske nam 25, 11800, Praha 1, Czech Republic

   Jan Kratochvíl , Jiří Fiala  & Petr Kolman ,  & 

2. State Key Lab. of Computer Science, Institute of Software,, Chinese Academy of Sciences, 100190, Beijing, P.R. China

   Angsheng Li

Reprints and permissions

© 2010 Springer-Verlag Berlin Heidelberg

Policies and ethics