Minimum Light Numbers in the $\sigma $-Game and Lit-Only $\sigma $-Game on Unicyclic and Grid Graphs
Document Type
Article
Publication Date
2011
Abstract
Consider a graph each of whose vertices is either in the ON state or in the OFF state and call the resulting ordered bipartition into ON vertices and OFF vertices a configuration of the graph. A regular move at a vertex changes the states of the neighbors of that vertex and hence sends the current configuration to another one. A valid move is a regular move at an ON vertex. For any graph $G,$ let $\mathcal{D}(G)$ be the minimum integer such that given any starting configuration $\bf x$ of $G$ there must exist a sequence of valid moves which takes $\bf x$ to a configuration with at most $\ell +\mathcal{D}(G)$ ON vertices provided there is a sequence of regular moves which brings $\bf x$ to a configuration in which there are $\ell$ ON vertices. The shadow graph $\mathcal{S}(G)$ of a graph $G$ is obtained from $G$ by deleting all loops. We prove that $\mathcal{D}(G)\leq 3$ if $\mathcal{S}(G)$ is unicyclic and give an example to show that the bound $3$ is tight. We also prove that $\mathcal{D}(G)\leq 2$ if $ G $ is a two-dimensional grid graph and $\mathcal{D}(G)=0$ if $\mathcal{S}(G)$ is a two-dimensional grid graph but not a path and $G\neq \mathcal{S}(G)$.
Digital Commons Citation
Goldwasser, John; Wang, Xinmao; and Yaokun Wu, "Minimum Light Numbers in the $\sigma $-Game and Lit-Only $\sigma $-Game on Unicyclic and Grid Graphs" (2011). Faculty & Staff Scholarship. 229.
https://researchrepository.wvu.edu/faculty_publications/229
Source Citation
John Goldwasser, ., Xinmao Wang, ., & Yaokun Wu, . (2011). Minimum Light Numbers In The $\Sigma $-Game And Lit-Only $\Sigma $-Game On Unicyclic And Grid Graphs. The Electronic Journal of Combinatorics, 18(1), P214.