Mathematics – Combinatorics
Scientific paper
2010-10-28
Mathematics
Combinatorics
20 pages
Scientific paper
Let $\Gamma=(S,R)$ denote a finite simple graph with vertex set $S$ and edge set $R.$ A configuration of the lit-only $\sigma$-game on $\Gamma$ is an assignment of one of two states, {\it on} or {\it off}, to all vertices of $\Gamma.$ Given a configuration, a move of the lit-only $\sigma$-game on $\Gamma$ allows the player to choose one {\it on} vertex $s$ of $\Gamma$ and change the states of all neighbors of $s.$ Given a starting configuration, the goal is usually to minimize the number of {\it on} vertices of $\Gamma$ or to reach an assigned configuration by a finite sequence of moves. Let $k\geq 1$ be an integer. We say that $\Gamma$ is $k$-lit whenever for any configuration, the number of {\it on} vertices can be reduced to at most $k$ by a finite sequence of moves. From the view of algebra we distinguish finite simple graphs into degenerate and nondegenerate classes. In this paper we obtain the following results. Assume that $\Gamma=(S,R)$ is a nondegenerate tree. We show that $\Gamma$ is 1-lit. Let $x,y\in S$ with $xy\in R.$ Let $f_x$ and $f_y$ denote the configurations with exactly one {\it on} vertex $x$ and exactly one {\it on} vertex $y,$ respectively. Assume that $f_x$ is not obtained from $f_y$ by any finite sequence of moves. Then the tree obtained from $\Gamma$ by inserting a new vertex on the edge $xy$ is 1-lit.
No associations
LandOfFree
Some one-lit trees for lit-only sigma-game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Some one-lit trees for lit-only sigma-game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some one-lit trees for lit-only sigma-game will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-582886