We study the following combinatorial game played by two players, Alice and Bob Given a connected graph G with nonnegative weights assigned to its vertices, the players alternately take one vertex of G 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 of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G 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 e>0 and for every k≥1 there is a k-connected graph G for which Bob has a strategy to obtain (1−e) 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.#R##N##R##N#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.
['Josef Cibulka', 'Jan Kynčl', 'Viola Mészáros', 'Rudolf Stolař', 'Pavel Valtr']
Graph sharing games: complexity and connectivity