Lit-only sigma-game on nondegenerate graphs
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.
nondegenerate graph lit-only \(\sigma \)-game group action primary 05c57 secondary 15a63 20f55