- Title
- A lower bound on the zero forcing number
- Creator
- Davila, Randy; Kalinowski, Thomas; Stephen, Sudeep
- Relation
- Discrete Applied Mathematics Vol. 250, Issue 11 December 2018, p. 363-367
- Publisher Link
- http://dx.doi.org/10.1016/j.dam.2018.04.015
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2018
- Description
- 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, d≥2, thereby settling the conjecture.
- Subject
- zero forcing; propagation in graphs
- Identifier
- http://hdl.handle.net/1959.13/1400575
- Identifier
- uon:34786
- Identifier
- ISSN:0166-218X
- Rights
- ©2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
- Language
- eng
- Full Text
- Reviewed
- Hits: 1982
- Visitors: 2360
- Downloads: 244
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 222 KB | Adobe Acrobat PDF | View Details Download |