Illuminating a Graph

We introduce a two-player game where the goal is to illuminate all edges of a graph. At each step the first player, called Illuminator, taps a vertex. The second player, called Adversary, reveals the edges incident with that vertex (consistent with the edges incident with the already tapped vertices). Illuminator tries to minimize the taps needed, and the value of the game is the number of taps needed with optimal play. We provide bounds on the value in trees and general graphs. In particular, we show that the value for the path on n vertices is 2 3 n + O ( 1 ) , and there is a constant ε > 0 such that for every caterpillar on n vertices, the value is at most ( 1 – ε ) n + 1 .