Some bounds on the zero forcing number of a graph
Some bounds on the zero forcing number of a graph
复制标题
DOI：
10.1016/j.dam.2017.11.015
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
Michael Gentner;D. Rautenbach
中科院分区：
文献类型：
--
作者：
Michael Gentner;D. Rautenbach
一个图G的顶点集Z是G的迫零集，如果最初将Z中的所有顶点标记为0，并将G的所有剩余顶点标记为1，然后迭代地尽可能长地将某个顶点u的标记从1变为0，如果u是某个标记为0的顶点的唯一标记为1的邻居，则导致G的所有顶点都具有标记0。迫零数Z（G）定义为G的迫零集的最小阶数，它被认为是与G相关的矩阵的余秩的上界，也被认为与量子物理和逻辑电路有关。考虑到迫零数的计算难度，上界和下界是有意义的。对Amos，Caro，Davila和Pepper的结果进行了改进，证明了对于n阶连通图G，最大度Δ至少为3，Z（G）≤ Δ− 2 Δ− 1 n当且仅当G不属于{K Δ+ 1，K Δ，Δ，K Δ− 1，Δ，G1，G2}，其中G1和G2分别是5阶和7阶的两个特殊图.对于阶数为n，最大度为3，围长至少为5的连通图G，我们证明Z（G）≤ n 2− Ω n log n。利用概率论证明了对于围长至少为5的n阶r-正则图G，Z（G）≤ 1− Hrr + oHrrn，其中Hr是r次调和数.最后，我们证明了对于围长g∈{5，6}，最小度δ的图G，Z（G）≥（g− 2）（δ− 2）+ 2，这部分地证实了Davila和Kenter的一个猜想.
A set Z of vertices of a graph G is a zero forcing set of G if initially labeling all vertices in Z with 0 and all remaining vertices of G with 1, and then, iteratively and as long as possible, changing the label of some vertex u from 1 to 0 if u is the only neighbor with label 1 of some vertex with label 0, results in all vertices of G having label 0. The zero forcing number Z (G), defined as the minimum order of a zero forcing set of G, was proposed as an upper bound of the corank of matrices associated with G, and was also considered in connection with quantum physics and logic circuits. In view of the computational hardness of the zero forcing number, upper and lower bounds are of interest. Refining results of Amos, Caro, Davila, and Pepper, we show that Z (G)≤ Δ− 2 Δ− 1 n for a connected graph G of order n and maximum degree Δ at least 3 if and only if G does not belong to {K Δ+ 1, K Δ, Δ, K Δ− 1, Δ, G 1, G 2}, where G 1 and G 2 are two specific graphs of orders 5 and 7, respectively. For a connected graph G of order n, maximum degree 3, and girth at least 5, we show Z (G)≤ n 2− Ω n log n. Using a probabilistic argument, we show Z (G)≤ 1− H r r+ o H r r n for an r-regular graph G of order n and girth at least 5, where H r is the r th harmonic number. Finally, we show that Z (G)≥(g− 2)(δ− 2)+ 2 for a graph G of girth g∈{5, 6} and minimum degree δ, which partially confirms a conjecture of Davila and Kenter.