Difference between minimum light numbers of sigma-game and lit-only sigma-game - Mathematics > CombinatoricsReport as inadecuate




Difference between minimum light numbers of sigma-game and lit-only sigma-game - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

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 theneighbors of that vertex. A valid move is a regular move at an on vertex. Thefollowing 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 anotherconfiguration in which there are $\ell$ on vertices then there must exist asequence 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$ issharp. Some relevant results and conjectures are also reported.



Author: Xinmao Wang, Yaokun Wu

Source: https://arxiv.org/



DOWNLOAD PDF




Related documents