Note on the lamp lighting problem

DOI10.1006/AAMA.2001.0739MaRDI QIDQ5956771zbMATH OpenOpenAlexFDO

Authors Henrik Eriksson, Kimmo Eriksson, Jonas Sjöstrand

Publication date 16 June 2002

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0411201

zbMATH Keywords

tilingsmatchingslamp lighting

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Matrices, determinants in number theory (11C20) Matrices of integers (15B36) Combinatorial aspects of tessellation and tiling problems (05B45) Cellular automata (computational aspects) (68Q80) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Abstract: We answer some questions concerning the so called sigma-game of Sutner. It is played on a graph where each vertex has a lamp, the light of which is toggled by pressing any vertex with an edge directed to the lamp. For example, we show that every configuration of lamps can be lit if and only if the number of complete matchings in the graph is odd. In the special case of an orthogonal grid one gets a criterion for whether the number of monomer-dimer tilings of an m times n grid is odd or even.

Recommendations

• scientific article; zbMATH DE number 700992
• scientific article; zbMATH DE number 67624
• The Floodlight Problem
• Revisiting Lambert's problem
• A counterexample to the lights out problem
• On the solution to every Lambert problem

Cites work

• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• Characterizing switch-setting problems^∗
• Linear cellular automata and the garden-of-eden
• Merlin's Magic Square
• Merlin's Magic Square Revisited
• The σ-Game and Cellular Automata
• \(\sigma\)-Automata and Chebyshev-polynomials
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata

Cited in

(19)

• Lights Out On A Random Graph
• Effects of edge addition or removal on the nullity of a graph
• Solutions to all-colors problem on graph cellular automata
• The edge-flipping group of a graph
• Construction of \(\sigma^+\)-game solutions on a rectangular grid
• The general \(\sigma \) all-ones problem for trees
• Universal configurations in light-flipping games
• Minimum light number of lit-only \(\sigma\)-game on a tree
• Lit-only sigma game on a line graph
• Completely symmetric configurations for \(\sigma \)-games on grid graphs
• Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs
• Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
• Lit-only \(\sigma \)-game on pseudo-trees
• Maximum orbit weights in the \(\sigma \)-game and lit-only \(\sigma \)-game on grids and graphs
• Chasing the lights in Lights Out
• A Survey of the Game “Lights Out!”
• On the complexity of dominating set problems related to the minimum all-ones problem
• ``Lights Out and variants
• Generalized switch-setting problems

This page was built for publication: Note on the lamp lighting problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956771)