Extremal values and bounds for the zero forcing number
Extremal values and bounds for the zero forcing number
复制标题
DOI：
10.1016/j.dam.2016.06.004
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
Michael Gentner;L. Penso;D. Rautenbach;U. Souza
中科院分区：
文献类型：
--
作者：
Michael Gentner;L. Penso;D. Rautenbach;U. Souza
图G的顶点集合Z是一个零迫使组G如果迭代添加Z顶点V (G)∖Z中独特的邻居的某个顶点V (G)∖Z Z,导致整个顶点集V (G)的G G的零迫使数Z (G)的最低基数是一套零迫使G·阿莫斯et al。(2015)证明Z (G)≤((Δ−2)n + 2) /(Δ−1)的连通图G n和最大程度Δ≥2。验证他们的猜想，我们证明了cn， K n和K Δ， Δ是这个不等式的唯一极值图。我们证实了Davila和Kenter[5]的一个猜想，证明了对于最小度δ≥2的任意无三角形图G， Z (G)≥2 δ−2。已知对于每一个图G，其中P (G)为G中顶点集划分V (G)的诱导路径的最小个数，则Z (G)≥P (G)。研究了一类图G，其中G的每个诱导子图H满足Z (H)= P (H)。
A set Z of vertices of a graph G is a zero forcing set of G if iteratively adding to Z vertices from V (G)∖ Z that are the unique neighbor in V (G)∖ Z of some vertex in Z, results in the entire vertex set V (G) of G. The zero forcing number Z (G) of G is the minimum cardinality of a zero forcing set of G. Amos et al.(2015) proved Z (G)≤((Δ− 2) n+ 2)/(Δ− 1) for a connected graph G of order n and maximum degree Δ≥ 2. Verifying their conjecture, we show that C n, K n, and K Δ, Δ are the only extremal graphs for this inequality. Confirming a conjecture of Davila and Kenter [5], we show that Z (G)≥ 2 δ− 2 for every triangle-free graph G of minimum degree δ≥ 2. It is known that Z (G)≥ P (G) for every graph G where P (G) is the minimum number of induced paths in G whose vertex sets partition V (G). We study the class of graphs G for which every induced subgraph H of G satisfies Z (H)= P (H).