Lit-only sigma-game on nondegenerate graphs
Journal of Algebraic Combinatorics, Tome 41 (2015) no. 2, pp. 385-395.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

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.
Classification : 05C57, 15A63, 20F55
Keywords: group action, lit-only $\sigma$-game, nondegenerate graph
@article{JAC_2015__41_2_a5,
     author = {Huang, Hau-Wen},
     title = {Lit-only sigma-game on nondegenerate graphs},
     journal = {Journal of Algebraic Combinatorics},
     pages = {385--395},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2015__41_2_a5/}
}
TY  - JOUR
AU  - Huang, Hau-Wen
TI  - Lit-only sigma-game on nondegenerate graphs
JO  - Journal of Algebraic Combinatorics
PY  - 2015
SP  - 385
EP  - 395
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2015__41_2_a5/
LA  - en
ID  - JAC_2015__41_2_a5
ER  - 
%0 Journal Article
%A Huang, Hau-Wen
%T Lit-only sigma-game on nondegenerate graphs
%J Journal of Algebraic Combinatorics
%D 2015
%P 385-395
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2015__41_2_a5/
%G en
%F JAC_2015__41_2_a5
Huang, Hau-Wen. Lit-only sigma-game on nondegenerate graphs. Journal of Algebraic Combinatorics, Tome 41 (2015) no. 2, pp. 385-395. http://geodesic.mathdoc.fr/item/JAC_2015__41_2_a5/