Minimum light number of lit-only -game on a tree

DOI10.1016/J.TCS.2007.05.033zbMATH Open1188.68207arXiv0904.3050OpenAlexW2050815478MaRDI QIDQ995589FDOQ995589

Yaokun Wu, Xinmao Wang

Publication date: 3 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A configuration of a graph is an assignment of one of two states, on or off, to each vertex of it. A regular move at a vertex changes the states of the neighbors of that vertex. A valid move is a regular move at an on vertex. The following result is proved in this note: given any starting configuration $x$ of a tree, if there is a sequence of regular moves which brings $x$ to another configuration in which there are $ell$ on vertices then there must exist a sequence of valid moves which takes $x$ to a configuration with at most $ell+2$ on vertices. We provide example to show that the upper bound $ell+2$ is sharp. Some relevant results and conjectures are also reported.

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

zbMATH Keywords

orbitHamming weightleavesbinary field

Mathematics Subject Classification ID

Trees (05C05) Combinatorics in computer science (68R05) Games involving graphs (91A43)

Cites Work

• Linear cellular automata and the garden-of-eden
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Extended Vogan diagrams
• Title not available (Why is that?)
• Parity dimension for graphs
• \(\sigma\)-Automata and Chebyshev-polynomials
• Lit-only sigma game on a line graph
• Characterizing switch-setting problems^∗
• Parity Dimension for Graphs - A Linear Algebraic Approach
• Title not available (Why is that?)
• The σ-Game and Cellular Automata
• Multidimensional \(\sigma\)-automata, \(\pi\)-polynomials and generalised S-matrices
• On a modular domination game.
• Chebyshev polynomials over finite fields and reversibility of \(\sigma\)-automata on square grids
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata
• Note on the lamp lighting problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equivalence classes of Vogan diagrams
• Puzzlers' tribute. A feast for the mind
• Deterministic one-dimensional cellular automata
• The Minimum All-Ones Problem for Trees
• Title not available (Why is that?)
• Linear cellular automata with boundary conditions
• On irreversibility of von Neumann additive cellular automata on grids
• Linear algebraic approach on real \(\sigma\)-game
• Decomposition of additive cellular automata

Cited In (8)

• Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
• Lit-only \(\sigma \)-game on pseudo-trees
• Lit-only sigma game on a line graph
• The edge-flipping group of a graph
• Maximum orbit weights in the \(\sigma \)-game and lit-only \(\sigma \)-game on grids and graphs
• The flipping puzzle on a graph
• Two-lit trees for lit-only \(\sigma \)-game
• Lit-only sigma-game on nondegenerate graphs

This page was built for publication: Minimum light number of lit-only \(\sigma\)-game on a tree

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