TCS Journal 2007 Journal Article
Minimum light number of lit-only σ -game on a tree
- Xinmao Wang
- Yaokun Wu
Let T be a tree with ℓ leaves. Each vertex of T is assigned a state either lit or off. An assignment of states to all the vertices of T is called a configuration. The lit-only σ -game allows the player to pick a lit vertex and change the states of all its neighbours. We prove that for any initial configuration one can make a sequence of allowable moves to arrive at a configuration in which the number of lit vertices is no greater than ⌈ ℓ 2 ⌉. We also give examples to show that the bound ⌈ ℓ 2 ⌉ cannot be relaxed to ⌊ ℓ 2 ⌋.