Lit-only sigma-game on nondegenerate graphs

Abstract

A configuration of the lit-only $σ$-game on a graph $Γ$ is an assignment of one of two states, {\it on} or {\it off}, to each vertex of $Γ.$ Given a configuration, a move of the lit-only $σ$-game on $Γ$ allows the player to choose an {\it on} vertex $s$ of $Γ$ and change the states of all neighbors of $s.$ Given an integer $k$, the underlying graph $Γ$ is said to be $k$-lit if for any configuration, the number of {\it 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 $σ$-game on nondegenerate graphs $Γ$ which are not line graphs. We show that these graphs $Γ$ are 2-lit and provide a linear algebraic criterion for $Γ$ to be 1-lit.