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 |
---|---|
Abstract | 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. |
Keywords | zero forcing; propagation in graphs |
Year | 2018 |
Journal | Discrete Applied Mathematics |
Journal citation | 250, pp. 363-367 |
Publisher | Elsevier B.V. |
ISSN | 0166-218X |
Digital Object Identifier (DOI) | https://doi.org/10.1016/j.dam.2018.04.015 |
Scopus EID | 2-s2.0-85046868489 |
Page range | 363-367 |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
Online | 14 Aug 2018 |
Publication process dates | |
Accepted | 06 Apr 2018 |
Deposited | 17 Nov 2023 |
https://acuresearchbank.acu.edu.au/item/8zz3v/a-lower-bound-on-the-zero-forcing-number
Restricted files
Publisher's version
31
total views0
total downloads2
views this month0
downloads this month