Note on the lamp lighting problem

DOI10.1006/AAMA.2001.0739zbMATH Open0995.05096arXivmath/0411201OpenAlexW1981580454MaRDI QIDQ5956771FDOQ5956771

Authors: Henrik Eriksson, Kimmo Eriksson, Jonas Sjöstrand 

Publication date: 16 June 2002

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

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.

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

Recommendations

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

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)

Cites Work

• Linear cellular automata and the garden-of-eden
• Title not available (Why is that?)
• \(\sigma\)-Automata and Chebyshev-polynomials
• Characterizing switch-setting problems^∗
• The σ-Game and Cellular Automata
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata
• Merlin's Magic Square
• Merlin's Magic Square Revisited

Cited In (19)

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

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)