Geodesic
A Short Proof for a Lower Bound on the Zero Forcing Number
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 355-360.

Voir la notice de l'article provenant de la source Library of Science

We provide a short proof of a conjecture of Davila and Kenter concerning a lower bound on the zero forcing number Z(G) of a graph G. More specifically, we show that Z(G) ≥ (g − 2)(δ − 2) + 2 for every graph G of girth g at least 3 and minimum degree δ at least 2.
Keywords: zero forcing, girth, Moore bound 
@article{DMGT_2020_40_1_a24,
     author = {F\"urst, Maximilian and Rautenbach, Dieter},
     title = {A {Short} {Proof} for a {Lower} {Bound} on the {Zero} {Forcing} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {355--360},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a24/}
}
TY  - JOUR
AU  - Fürst, Maximilian
AU  - Rautenbach, Dieter
TI  - A Short Proof for a Lower Bound on the Zero Forcing Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 355
EP  - 360
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a24/
LA  - en
ID  - DMGT_2020_40_1_a24
ER  - 
%0 Journal Article
%A Fürst, Maximilian
%A Rautenbach, Dieter
%T A Short Proof for a Lower Bound on the Zero Forcing Number
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 355-360
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a24/
%G en
%F DMGT_2020_40_1_a24
Fürst, Maximilian; Rautenbach, Dieter. A Short Proof for a Lower Bound on the Zero Forcing Number. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 355-360. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a24/

[1] AIM Minimum Rank - Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. Cioabă, D. Cvetković, S. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, H. van der Holst, K.V. Meulen and A.W. Wehe), Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628–1648. doi:10.1016/j.laa.2007.10.009

[2] N. Alon, S. Hoory and N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18 (2002) 53–57. doi:10.1007/s003730200002

[3] F. Barioli, W. Barrett, S. Fallat, H.T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory 72 (2013) 146–177. doi:10.1002/jgt.21637

[4] A. Berman, S. Friedland, L. Hogben, U.G. Rothblum and B. Shader, An upper bound for the minimum rank of a graph, Linear Algebra Appl. 429 (2008) 1629–1638. doi:10.1016/j.laa.2008.04.038

[5] D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett. 99 (2007) 100501. doi:10.1103/PhysRevLett.99.100501

[6] D. Burgarth, V. Giovannetti, L. Hogben, S. Severini and M. Young, Logic circuits from zero forcing, Nat. Comput. 14 (2015) 485–490. doi:10.1007/s11047-014-9438-5

[7] D. Burgarth and K. Maruyama, Indirect Hamiltonian identification through a small gateway, New J. Phys. 11 (2009) 103019. doi:10.1088/1367-2630/11/10/103019

[8] L.S. Chandran and C.R. Subramanian, Girth and treewidth, J. Combin. Theory Ser. B 93 (2005) 23–32. doi:10.1016/j.jctb.2004.05.004

[9] R. Davila and M. Henning, The forcing number of graphs with given girth, arXiv:1610.08435v1.

[10] R. Davila, T. Kalinowski and S. Stephen, Proof of a conjecture of Davila and Kenter regarding a lower bound for the forcing number in terms of girth and minimum degree . arXiv:1611.06557v2

[11] R. Davila and F. Kenter, Bounds for the zero forcing number of graphs with large girth, Theory Appl. Graphs 2 ( 2 ) (2015) Art. 1. doi:10.20429/tag.2015.020201

[12] M. Gentner, L.D. Penso, D. Rautenbach and U.S. Souza, Extremal values and bounds for the zero forcing number, Discrete Appl. Math. 214 (2016) 196–200. doi:10.1016/j.dam.2016.06.004

[13] M. Gentner and D. Rautenbach, Some bounds on the zero forcing number of a graph, Discrete Appl. Math. 236 (2018) 203–213. doi:10.1016/j.dam.2017.11.015

[14] S. Severini, Nondiscriminatory propagation on trees, J. Phys. A 41 (2008) 48. doi:10.1088/1751-8113/41/48/482002