Proof of a conjecture on the zero forcing number of a graph
Proof of a conjecture on the zero forcing number of a graph
复制标题
图的迫零数猜想的证明
DOI：
10.1016/j.dam.2016.05.009
复制
发表时间：
2015-07
影响因子：
1.1
通讯作者：
Zixing Tang
中科院分区：
文献类型：
--
作者：
Leihao Lu;Baoyindureng Wu;Zixing Tang
Amos等人(2015)引入了正整数k的图的k-强迫数的概念，作为图的零强迫数的推广。简单图G的k-强制数，记为Fk(G)，是需要初始着色以使所有顶点在由下列规则定义的离散动态过程中最终变为着色的最小顶点数。从一组初始的有色顶点开始，当所有顶点都有颜色时停止：如果一个有颜色的顶点至多有k个非颜色的邻居，那么它的每个非颜色的邻居都会变成有颜色的。特别地，由于F1(G)与图的最大零度密切相关，所以F1(G)在Z(G)的名称下被广泛地研究。除其他外，Amos等人。证明了对于具有Δ=Δ(G)≥2，Z(G)≤(Δ−2)n+2Δ−1的n阶连通图G，这个不等式是尖锐的。此外，他们还猜想Z(G)=(Δ−2)n+2Δ−1当且仅当G=Cn，G=KΔ+1或G=KΔ，Δ。在这个注解中，我们证明了上述猜想是正确的。
Abstract Amos et al.(2015) introduced the notion of the k-forcing number of graph for a positive integer k as the generalization of the zero forcing number of a graph. The k-forcing number of a simple graph G, denoted by F k (G), is the minimum number of vertices that need to be initially colored so that all vertices eventually become colored during the discrete dynamical process defined by the following rule. Starting from an initial set of colored vertices and stopping when all vertices are colored: if a colored vertex has at most k non-colored neighbors, then each of its non-colored neighbors become colored. Particularly, with a close connection to the maximum nullity of a graph, F 1 (G) is widely studied under the name of the zero forcing number, denoted by Z (G). Among other things, Amos et al. proved that for a connected graph G of order n with Δ= Δ (G)≥ 2, Z (G)≤(Δ− 2) n+ 2 Δ− 1, and this inequality is sharp. Moreover, they conjectured that Z (G)=(Δ− 2) n+ 2 Δ− 1 if and only if G= C n, G= K Δ+ 1 or G= K Δ, Δ. In this note, we show the above conjecture is true.
登录
查看更多内容
DOI：
10.20429/tag.2015.020202
发表时间：
2014-05
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
Y. Caro;R. Pepper
通讯作者：
Y. Caro;R. Pepper
DOI：
10.1007/s10114-017-4699-4
发表时间：
2017-02
期刊：
Acta Mathematica Sinica, English Series
影响因子：
--
作者：
Linda Eroh;Cong X. Kang;Eunjeong Yi
通讯作者：
Linda Eroh;Cong X. Kang;Eunjeong Yi
影响因子：
1.1
作者：
Seth A. Meyer
通讯作者：
Seth A. Meyer
影响因子：
1.1
作者：
Shaun M. Fallat;L. Hogben
通讯作者：
Shaun M. Fallat;L. Hogben
影响因子：
6.3
作者：
W. Haemers
通讯作者：
W. Haemers