Document Type


Publication Date



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)$.

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.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.