Davila, Randy

Kalinowski, Thomas

Stephen, Sudeep

2018-12-11

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.

Discrete Applied Mathematics, v.250, p. 363-367

1872-6771

0166-218X

https://hdl.handle.net/1959.11/26506

Elsevier BV, North-Holland

A lower bound on the zero forcing number

Journal Article

Publication