# A lower bound on the zero forcing number

Journal article

Davila, Randy, Kalinowski, Thomas and Stephen, Sudeep. (2018). A lower bound on the zero forcing number. Discrete Applied Mathematics. 250, pp. 363-367. https://doi.org/10.1016/j.dam.2018.04.015
Authors Davila, Randy, Kalinowski, Thomas and Stephen, Sudeep In this note, we study a dynamic vertex coloring for a graph G. In particular, one starts with a certain set of vertices black, and all other vertices white. Then, at each time step, a black vertex with exactly one white neighbor forces its white neighbor to become black. The initial set of black vertices is called a zero forcing set if by iterating this process, all of the vertices in G become black. The zero forcing number of G is the minimum cardinality of a zero forcing set in G, and is denoted by Z(G). Davila and Kenter have conjectured in 2015 that Z(G) ≥ (g −3)(δ −2)+δ where g and δ denote the girth and the minimum degree of G, respectively. This conjecture has been proven for graphs with girth g ≤ 10. In this note, we present a proof for g ≥ 5, δ ≥ 2, thereby settling the conjecture. zero forcing; propagation in graphs 2018 Discrete Applied Mathematics 250, pp. 363-367 Elsevier B.V. 0166-218X https://doi.org/10.1016/j.dam.2018.04.015 2-s2.0-85046868489 363-367 LicenseAll rights reservedFile Access LevelControlled Published 14 Aug 2018 06 Apr 2018 17 Nov 2023

https://acuresearchbank.acu.edu.au/item/8zz3v/a-lower-bound-on-the-zero-forcing-number

## Restricted files

### Publisher's version

total views
• ##### 0
views this month
• ##### 0
These values are for the period from 19th October 2020, when this repository was created.

## Related outputs

##### Zero forcing in iterated line digraphs
Ferrero, Daniela, Kalinowski, Thomas and Stephen, Sudeep. (2019). Zero forcing in iterated line digraphs. Discrete Applied Mathematics. 255, pp. 198-208. https://doi.org/10.1016/j.dam.2018.08.019
##### Minimum rank and zero forcing number for butterfly networks
Ferrero, Daniela, Grigorious, Cyriac, Kalinowski, Thomas, Ryan, Joe and Stephen, Sudeep. (2019). Minimum rank and zero forcing number for butterfly networks. Journal of Combinatorial Optimization. 37(3), pp. 970-988. https://doi.org/10.1007/s10878-018-0335-1
##### Average distance in interconnection networks via reduction theorems for vertex-weighted graphs
Klavžar, Sandi, Manuel, Paul, Nadjafi-Arani, M. J., Rajan, R. Sundara, Grigorious, Cyriac and Stephen, Sudeep. (2016). Average distance in interconnection networks via reduction theorems for vertex-weighted graphs. The Computer Journal. 59(12), pp. 1900-1910. https://doi.org/10.1093/comjnl/bxw046
##### Resolving-power dominating sets
Stephen, Sudeep, Rajan, Bharati, Grigorious, Cyriac and William, Albert. (2015). Resolving-power dominating sets. Applied Mathematics and Computation. 256, pp. 778-785. https://doi.org/10.1016/j.amc.2015.01.037
##### On the Strong Metric Dimension of Tetrahedral Diamond Lattice
Manuel, Paul, Rajan, Bharati, Grigorious, Cyriac and Stephen, Sudeep. (2015). On the Strong Metric Dimension of Tetrahedral Diamond Lattice. Mathematics in Computer Science. 9(2), pp. 201-208. https://doi.org/10.1007/s11786-015-0226-0
##### Power domination in certain chemical structures
Stephen, Sudeep, Rajan, Bharati, Ryan, Joe, Grigorious, Cyriac and William, Albert. (2015). Power domination in certain chemical structures. Journal of Discrete Algorithms (Amsterdam). 33, pp. 10-18. https://doi.org/10.1016/j.jda.2014.12.003
##### On the metric dimension of circulant and Harary graphs
Grigorious, Cyriac, Manuel, Paul, Miller, Mirka, Rajan, Bharati and Stephen, Sudeep. (2014). On the metric dimension of circulant and Harary graphs. Applied Mathematics and Computation. 248, pp. 47-54. https://doi.org/10.1016/j.amc.2014.09.045
##### On the partition dimension of a class of circulant graphs
Grigorious, Cyriac, Stephen, Sudeep, Rajan, Bharati, Miller, Mirka and William, Albert. (2014). On the partition dimension of a class of circulant graphs. Information Processing Letters. 114(7), pp. 353-356. https://doi.org/10.1016/j.ipl.2014.02.005