Tag game on graphs

48 Views Asked by At

Inspired by this question.

This game is played on an arbitrary graph. Player 1 starts by choosing a vertex. Then alternate:

  1. Player 2 selects a set of $n$ vertices of the graph. Player 1 loses if they are on any of these.
  2. Otherwise, player 1 moves from their current vertex to one of its neighbours. Player 2 learns nothing other than that the game hasn't ended.

What is the minimum $n$ such that player 2 wins?

WOLOG, the graph is connected and simple. As @Tavish notes, the only way to make progress is to completely eliminate vertices; but the eliminated set need not be monotonic per turn. $n$ itself is monotonic under induced subgraphs.

Several interesting cases to consider:

  1. The infinite star: $n=1$
  2. $k$ triangles joined at a common vertex (or the $2k$-star, with leaves paired): $n=2$
  3. Two infinite stars with their roots connected: $n=1$
  4. The $k$-path, $k\geq5$: n=2 $n=1$ still
  5. The 5-cycle with one vertex exploded into $k$ unconnected vertices: $n=2$
  6. The $k$-cycle, $k\geq6$: n=3 $n=2$ still
  7. An induced subgraph of minimum degree $k$: $n\geq k$

So it seems path length plays a complicated role here, not just degree.

Here's an easy upper bound:

Arbitrarily order the vertices. Maintain two sets, called the burned set and the current-tag set; both start out empty.

  1. Pick the earliest unburned vertex, and add it and its unburned neighbours to the current-tag set.
  2. Tag all of the current-tag set this turn.
  3. Whenever a vertex and all its neighbours are all either burned or currently-tagged, burn that vertex and remove it from the current-tag set.
  4. Repeat.

Correctness invariant: player 1 may never be on a burned vertex.

Any stronger theorems?