Two-lit trees for lit-only sigma-game
classification
🧮 math.CO
keywords
gammaconfigurationlit-onlyfinitegamegivensigmastates
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.