Lit-only sigma-game on nondegenerate graphs
Hau-Wen Huang · Journal of Algebraic Combinatorics · 2014
A configuration of the lit-only $$\sigma $$ -game on a graph $$\Gamma $$ is an assignment of one of two states, on or off, to each vertex 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 an integer $$k$$ , the underlying graph $$\Gamma $$ is said to be $$k$$ -lit if for any configuration, the number of on vertices can be reduced to at most $$k$$ by a finite sequence of moves. We give a description of the orbits of the lit-only $$\sigma $$ -game on nondegenerate graphs $$\Gamma $$ which are not line graphs. We show that these graphs $$\Gamma $$ are 2-lit and provide a linear algebraic criterion for $$\Gamma $$ to be 1-lit.