Please use this identifier to cite or link to this item:
https://hdl.handle.net/1959.11/26506
Title: | A lower bound on the zero forcing number | Contributor(s): | Davila, Randy (author); Kalinowski, Thomas (author) ; Stephen, Sudeep (author) | Publication Date: | 2018-12-11 | DOI: | 10.1016/j.dam.2018.04.015 | Handle Link: | https://hdl.handle.net/1959.11/26506 | 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. | Publication Type: | Journal Article | Source of Publication: | Discrete Applied Mathematics, v.250, p. 363-367 | Publisher: | Elsevier BV, North-Holland | Place of Publication: | Netherlands | ISSN: | 1872-6771 0166-218X |
Fields of Research (FoR) 2008: | 010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) | Fields of Research (FoR) 2020: | 490404 Combinatorics and discrete mathematics (excl. physical combinatorics) | Socio-Economic Objective (SEO) 2008: | 970101 Expanding Knowledge in the Mathematical Sciences | Socio-Economic Objective (SEO) 2020: | 280118 Expanding knowledge in the mathematical sciences | Peer Reviewed: | Yes | HERDC Category Description: | C1 Refereed Article in a Scholarly Journal |
---|---|
Appears in Collections: | Journal Article School of Science and Technology |
Files in This Item:
File | Size | Format |
---|
SCOPUSTM
Citations
21
checked on Mar 9, 2024
Page view(s)
1,244
checked on Mar 9, 2023
Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.