Completely symmetric configurations for -games on grid graphs

DOI10.1007/S10801-009-0199-7zbMATH Open1227.05199arXiv0903.0339OpenAlexW2016198570MaRDI QIDQ976843FDOQ976843

Authors: Mathieu Florence, Frédéric Meunier 

Publication date: 16 June 2010

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

Abstract: The paper deals with sigma-games on grid graphs (in dimension 2 and more) and conditions under which any completely symmetric configuration of lit vertices can be reached -- in particular the completely lit configuration -- when starting with the all-unlit configuration. The answer is complete in dimension 2. In dimension greater than or equal to 3, the answer is complete for the sigma^+ -game, and for the sigma^- -game if at least one of the sizes is even. The case sigma^-, dimension greater than or equal to 3 and all sizes odd remains open.

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

Recommendations

• Maximum orbit weights in the \(\sigma \)-game and lit-only \(\sigma \)-game on grids and graphs
• Note on the lamp lighting problem
• Two-lit trees for lit-only \(\sigma \)-game
• Minimum light numbers in the \(\sigma \)-game and lit-only \(\sigma \)-game on unicyclic and grid graphs
• Lit-only sigma-game on nondegenerate graphs

zbMATH Keywords

commutative algebragrid graphsChebychev polynomialssigma-games

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Games on graphs (graph-theoretic aspects) (05C57) Polynomials over finite fields (11T06)

Cites Work

• Linear cellular automata and the garden-of-eden
• Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
• \(\sigma\)-Automata and Chebyshev-polynomials
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata
• Parity dominating sets in grid graphs

Cited In (3)

• Construction of \(\sigma^+\)-game solutions on a rectangular grid
• On a modular domination game.
• Minimum light numbers in the \(\sigma \)-game and lit-only \(\sigma \)-game on unicyclic and grid graphs

This page was built for publication: Completely symmetric configurations for \(\sigma \)-games on grid graphs

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