  We study the following combinatorial game played by two players, Alice and
Bob, which generalizes the Pizza game considered by Brown, Winkler and others.
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 if rules (T) and/or
(R) are required then for every epsilon > 0 and for every positive integer k
there is a k-connected graph G for which Bob has a strategy to obtain
(1-epsilon) of the total weight of the vertices. This contrasts with the
original Pizza 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 game played on connected graphs (without weights) 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.
