Lights Out On A Random Graph

MaRDI QIDQ5045960zbMATH OpenFDO

Authors Bradley Forrest, Nicole Manno

Publication date 8 November 2022

Full work available at URL https://arxiv.org/abs/2108.07349, https://journals.calstate.edu/pump/article/view/2593

zbMATH Keywords

Lights OutMonte Carlorandom graph

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Games involving graphs (91A43)

Abstract: We consider the generalized game Lights Out played on a graph and investigate the following question: for a given positive integer $n$, what is the probability that a graph chosen uniformly at random from the set of graphs with $n$ vertices yields a universally solvable game of Lights Out? When $nleq11$, we compute this probability exactly by determining if the game is universally solvable for each graph with $n$ vertices. We approximate this probability for each positive integer $n$ with $nleq100$ by applying a Monte Carlo method using 1,000,000 trials. We also perform the analogous computations for connected graphs.

Cites work

• Characterizing switch-setting problems^∗
• Chebyshev polynomials over finite fields and reversibility of \(\sigma\)-automata on square grids
• scientific article; zbMATH DE number 6374006 (Why is no real title available?)
• scientific article; zbMATH DE number 436064 (Why is no real title available?)
• scientific article; zbMATH DE number 871170 (Why is no real title available?)
• Kombinatorische Anzahlbestimmungen in Relationen
• Lights Out for graphs related to one another by constructions
• Lights Out on finite graphs
• Linear cellular automata and the garden-of-eden
• Note on the lamp lighting problem
• On a modular domination game.
• On weight-one solvable configurations of the Lights Out puzzle
• Periodic harmonic functions on lattices and points count in positive characteristic
• Practical graph isomorphism. II.
• The random selection of unlabeled graphs
• The σ-Game and Cellular Automata

Cited in

(1)

• A recursive approach to a multi-state cylindrical lights out game

Describes a project that uses

Uses Software

• Traces
• OEIS
• nauty

This page was built for publication: Lights Out On A Random Graph

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