A characterization of always solvable trees in Lights Out game using the activation numbers of vertices
From MaRDI portal
Publication:6347378
arXiv2008.08541MaRDI QIDQ6347378FDOQ6347378
Authors: Ahmet Batal 
Publication date: 19 August 2020
Abstract: Lights out is a game that can be played on any simple graph . A configuration assigns one of the two states emph{on} or emph{off} to each vertex. For a given configuration, the aim of the game is to turn all vertices emph{off} by applying a push pattern on vertices, where each push switches the state of the vertex and its neighbors. If every configuration of vertices is solvable, then we say that the graph is always solvable. We introduce a concept which we call the activation numbers of vertices and we prove several characterization results of graphs by using this concept. We show that for every always solvable graph there exists a chain of always solvable subgraphs where each subgraph differs from the preceding one by a vertex. We also characterize always solvable trees by showing that all always solvable trees can be constructed from always solvable subtrees by some special types of connections. We call the dimension of the space of null-patterns, which leave configurations unchanged, the nullity of the graph . We show that the nullity of a tree can be characterized by the cardinality of its minimal partition into always solvable subtrees.
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Games on graphs (graph-theoretic aspects) (05C57)
This page was built for publication: A characterization of always solvable trees in Lights Out game using the activation numbers of vertices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6347378)
