pith. sign in

arxiv: 1010.5846 · v3 · pith:5OJIKXPYnew · submitted 2010-10-28 · 🧮 math.CO

Two-lit trees for lit-only sigma-game

classification 🧮 math.CO
keywords gammaconfigurationlit-onlyfinitegamegivensigmastates
0
0 comments X
read the original abstract

A configuration of the lit-only $\sigma$-game on a finite graph $\Gamma$ is an assignment of one of two states, on or off, to all vertices of $\Gamma.$ Given a configuration, a move of the lit-only $\sigma$-game on $\Gamma$ allows the player to choose an on vertex $s$ of $\Gamma$ and change the states of all neighbors of $s.$ Given any integer $k$, we say that $\Gamma$ is $k$-lit if, for any configuration, the number of on vertices can be reduced to at most $k$ by a finite sequence of moves. Assume that $\Gamma$ is a tree with a perfect matching. We show that $\Gamma$ is 1-lit and any tree obtained from $\Gamma$ by adding a new vertex on an edge of $\Gamma$ is 2-lit.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.