pith. sign in

arxiv: 1209.1233 · v1 · pith:WARXPAFSnew · submitted 2012-09-06 · 🧮 math.CO

Lit-only sigma-game on nondegenerate graphs

classification 🧮 math.CO
keywords gammagraphslit-onlyconfigurationgamesigmagivengraph
0
0 comments X
read the original abstract

A configuration of the lit-only $\sigma$-game on a graph $\Gamma$ is an assignment of one of two states, {\it on} or {\it 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 {\it 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 {\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 $\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.

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.