论文标题
在失败的零强迫数量上的下限图
A Lower Bound on the Failed Zero Forcing Number of a Graph
论文作者
论文摘要
给定图形$ g =（v，e）$和一组标记为填充的顶点，我们考虑一个称为零强迫的颜色变换规则。如果填充$ s $并应用了颜色更改规则的所有可能实例，则$ s $是零强制集，这会导致$ v $中的所有顶点。失败的零强迫集是一组并不是零强迫集的顶点。给定图形$ g $，失败的零强迫$ f（g）$是失败零强迫集的最大大小。一个开放的问题是，如果给出任何$ k $的$ \ ell $，以使所有至少$ \ ell $ dertices的图形都必须满足$ f（g）\ geq k $。我们通过证明$ n $ vertices的图$ g $肯定地回答了这个问题，$ f（g）\ geq \ lfloor \ frac \ frac {n-1} {2} {2} \ rfloor $。
Given a graph $G=(V,E)$ and a set of vertices marked as filled, we consider a color-change rule known as zero forcing. A set $S$ is a zero forcing set if filling $S$ and applying all possible instances of the color change rule causes all vertices in $V$ to be filled. A failed zero forcing set is a set of vertices that is not a zero forcing set. Given a graph $G$, the failed zero forcing number $F(G)$ is the maximum size of a failed zero forcing set. An open question was whether given any $k$ there is a an $\ell$ such that all graphs with at least $\ell$ vertices must satisfy $F(G)\geq k$. We answer this question affirmatively by proving that for a graph $G$ with $n$ vertices, $F(G)\geq \lfloor\frac{n-1}{2}\rfloor$.
