Lit-only sigma-game on nondegenerate graphs

Research output: Contribution to journalArticlepeer-review

Abstract

A configuration of the lit-only-game on a graph is an assignment of one of two states, on or off, to each vertex of. Given a configuration, a move of the lit-only-game on allows the player to choose an on vertex of and change the states of all neighbors of. Given an integer, the underlying graph is said to be-lit if for any configuration, the number of on vertices can be reduced to at most 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.

Original languageEnglish
Pages (from-to)385-395
Number of pages11
JournalJournal of Algebraic Combinatorics
Volume41
Issue number2
DOIs
StatePublished - Mar 2014

Keywords

  • Group action
  • Lit-only-game
  • Nondegenerate graph

Fingerprint

Dive into the research topics of 'Lit-only sigma-game on nondegenerate graphs'. Together they form a unique fingerprint.

Cite this