A lower bound on the failed zero-forcing number of a graph
A lower bound on the failed zero-forcing number of a graph
复制标题
图的失败迫零数的下界
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Nicolas Swanson
中科院分区：
文献类型：
--
作者：
Eric Ufferman;Nicolas Swanson
给定一个图$G=(V，E)$和一组标记为已填满的顶点，我们考虑一种称为强制零的颜色变化规则。集合$S$是零强制集，如果填充$S$并应用颜色变化规则的所有可能实例会导致填充$V$中的所有顶点。失败的迫零集合是不是迫零集合的顶点的集合。给定一个图$G$，失败的逼零数$F(G)$是失败的逼零集的最大大小。一个悬而未决的问题是，给定任何$k$，是否存在一个$ell$，使得所有至少有$ell$个顶点的图都必须满足$F(G)geq k$。我们肯定地回答了这个问题，证明了对于一个有$n$个顶点的图$G$，$F(G)geq lflorfrac{n-1}{2}
楼层$。
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 lfloorfrac{n-1}{2}
floor$.
所有具有失败的迫零数为 2 的图
DOI：
10.3390/sym13112221
发表时间：
2021
期刊：
Symmetry
影响因子：
--
作者：
Gomez, Luis;Rubi, Karla;Terrazas, Jorden;Narayan, Darren A.
通讯作者：
Narayan, Darren A.