Two-lit trees for lit-only σ-game

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

A configuration of the lit-only σ-game on a finite graph Γ is an assignment of one of two states, on or off, to all vertices of Γ. Given a configuration, a move of the lit-only σ-game on Γ allows the player to choose an on vertex s of Γ and change the states of all neighbors of s. Given any integer k, we say that Γ is k-lit if, for any configuration, the number of on vertices can be reduced to at most k by a finite sequence of moves. Assume that Γ is a tree with a perfect matching. We show that Γ is 1-lit and any tree obtained from Γ by adding a new vertex on an edge of Γ is 2-lit.

Original languageEnglish
Pages (from-to)1057-1066
Number of pages10
JournalLinear Algebra and Its Applications
Volume438
Issue number3
DOIs
StatePublished - 1 Feb 2013

Keywords

  • Group action
  • Lit-only σ-game
  • Symplectic forms

Fingerprint

Dive into the research topics of 'Two-lit trees for lit-only σ-game'. Together they form a unique fingerprint.

Cite this