论文标题
最低等级和零强迫图数量
Minimum rank and failed zero forcing number of graphs
论文作者
论文摘要
让$ g $成为一个简单，有限且无方向的图，每个顶点都给出了蓝色或白色的初始颜色。零强迫$ g $是一个迭代过程，即在有限应用指定的颜色变化规则后，迫使其白色顶点变为蓝色。我们说，如果指定的颜色变换规则，$ g $的蓝色顶点的初始套$ S $是$ g $的零强迫，如果有限数量的零迭代强迫结果对$ g $的所有顶点均为蓝色的更新颜色。否则，我们说$ s $在指定的颜色变化规则下是$ g $的零强迫设置。不难看到失败的零强迫集的任何子集也失败了。因此，我们的兴趣在于失败的零强迫集的最大可能的基数，我们称这是零强制$ g $的零强迫。在本文中，我们考虑了两个变色规则$ - $标准和积极的半决赛。我们计算了失败的零强迫数量的零。此外，在每个图形家族下，我们表征了图$ g $的零强迫数量等于$ g $的最低等级。
Let $G$ be a simple, finite, and undirected graph with vertices each given an initial coloring of either blue or white. Zero forcing on graph $G$ is an iterative process of forcing its white vertices to become blue after a finite application of a specified color-change rule. We say that an initial set $S$ of blue vertices of $G$ is a zero forcing set for $G$ under the specified color-change rule if a finite number of iterations of zero forcing results to an updated coloring where all vertices of $G$ are blue. Otherwise, we say that $S$ is a failed zero forcing set for $G$ under the specified color-change rule. It is not difficult to see that any subset of a failed zero forcing set is also failed. Hence, our interest lies on the maximum possible cardinality of a failed zero forcing set, which we refer to as the failed zero forcing number of $G$. In this paper, we consider two color-change rules $-$ standard and positive semidefinite. We compute for the failed zero forcing numbers of several graph families. Furthermore, under each graph family, we characterize the graphs $G$ for which the failed zero forcing number is equal to the minimum rank of $G$.
