Lit-only sigma-game on pseudo-trees
Lit-only sigma-game on pseudo-trees
复制标题
DOI：
10.1016/j.dam.2010.08.009
复制
发表时间：
2010-10
期刊：
影响因子：
--
通讯作者：
Xinmao Wang;Yaokun Wu
中科院分区：
文献类型：
--
作者：
Xinmao Wang;Yaokun Wu
一个图的构形是将两个状态之一（ON或OFF）分配给它的每个顶点。在一个顶点上的规则移动会改变该顶点的邻居的状态。有效移动是在ON顶点处的常规移动。伪树是从树通过附加零个或多个循环而获得的图。本文证明了如下结果：给定伪树的任意起始构形x，如果存在一个正规移动序列使x到达另一个构形，而该构形中的顶点数为N +2，则一定存在一个有效移动序列使x到达至多为N +2的构形.我们给出一个例子来说明上界ε +2是尖锐的。文中还介绍了有关问题和解决办法。
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 the neighbors of that vertex. A valid move is a regular move at an ON vertex. A pseudo-tree is a graph obtained from a tree by attaching zero or more loops. The following result is proved in this note: given any starting configuration x of a pseudo-tree, if there is a sequence of regular moves which brings x to another configuration in which there are ℓ ON vertices then there must exist a sequence of valid moves which takes x to a configuration with at most ℓ+2 ON vertices. We provide an example to show that the upper bound ℓ+2 is sharp. Some related problems and conjectures are also reported.