Minimum light number of lit-only σ-game on a tree
X Wang, Y Wu - Theoretical Computer Science, 2007 - Elsevier
X Wang, Y Wu
Theoretical Computer Science, 2007•ElsevierLet 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⌋.
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⌋.
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⌋.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果