Difference between minimum light numbers of sigma-game and lit-only sigma-game - Mathematics > Combinatorics

Difference between minimum light numbers of sigma-game and lit-only sigma-game - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Xinmao Wang, Yaokun Wu

Fuente: https://arxiv.org/