论文标题
使用顶点的激活类型在灯光中始终可解决的树的表征
A characterization of always solvable trees in the Lights Out game using the activation types of vertices
论文作者
论文摘要
Lights Out是可以在任何简单的图形$ G $上玩的游戏。配置将两个状态之一\ emph {on}或\ emph {off}分配给每个顶点。对于给定的配置，游戏的目的是通过在顶点上应用推动模式来转动所有顶点\ emph {off}，每个推动都会在其中切换顶点及其邻居的状态。如果可以解决顶点的每种配置，那么我们说该图始终可溶解。我们介绍了一个概念，我们称之为顶点的激活类型，并通过使用此概念证明了树的几个表征结果。我们表明，所有与星树不同的可解决树木总是可以看作是其两个始终可解决的子树的联接图。我们称为null-Patterns空间的尺寸，它们使配置保持不变，即图$ g $的无效。我们表明，树的无效可以以其最小分区的基础性为特征。我们还表明，树的无效小于其偶数顶点的数量。
Lights out is a game that can be played on any simple graph $G$. A configuration assigns one of the two states \emph{on} or \emph{off} to each vertex. For a given configuration, the aim of the game is to turn all vertices \emph{off} by applying a push pattern on vertices, where each push switches the state of the vertex and its neighbors. If every configuration of vertices is solvable, then we say that the graph is always solvable. We introduce a concept which we call the activation types of vertices and we prove several characterization results of trees by using this concept. We showed that all always solvable trees different than the star tree can be seen as the join graph of its two always solvable subtrees. We call the dimension of the space of null-patterns, which leave configurations unchanged, the nullity of the graph $G$. We show that the nullity of a tree can be characterized by the cardinality of its minimal partition into always solvable subtrees. We also showed that nullity of a tree is less than the number of its even degree vertices.
