A lower bound on the zero forcing number

DOI10.1016/J.DAM.2018.04.015MaRDI QIDQ1801082zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Randy Davila, Thomas Kalinowski, Sudeep Stephen

Publication date 26 October 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06557

zbMATH Keywords

propagation in graphszero forcing

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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 emph{zero forcing set} if by iterating this process, all of the vertices in $G$ become black. The emph{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)geq(g-3)(delta-2)+delta$ where $g$ and $delta$ denote the girth and the minimum degree of $G$, respectively. This conjecture has been proven for graphs with girth $gleq10$. In this note, we present a proof for $ggeq5$, $deltageq2$, thereby settling the conjecture.

Recommendations

• The forcing number of graphs with given girth
• A short proof for a lower bound on the zero forcing number
• Some bounds on the zero forcing number of a graph
• Proof of a conjecture on the zero forcing number of a graph
• Bounds for the Zero Forcing Number of Graphs with Large Girth

Cites work

• Bounds for the Zero Forcing Number of Graphs with Large Girth
• Exact value of \(\operatorname{ex}(n; \{C_3, \ldots, C_s \})\) for \(n \leq \lfloor \frac{25(s - 1)}{8} \rfloor\)
• Extremal values and bounds for the zero forcing number
• Graph theory
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Proof of a conjecture on the zero forcing number of a graph
• Some bounds on the zero forcing number of a graph
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited in

(30)

• Some bounds on the zero forcing number of a graph
• On the total forcing number of a graph
• Bounds on the connected forcing number of a graph
• Total forcing versus total domination in cubic graphs
• Zero forcing versus domination in cubic graphs
• Note on forcing problem of trees
• On the zero forcing number and spectral radius of graphs
• On the semitotal forcing number of a graph
• On the zero blocking number of rectangular, cylindrical, and Möbius grids
• Blocking zero forcing processes in Cartesian products of graphs
• A short proof for a lower bound on the zero forcing number
• On the zero forcing number of a graph involving some classical parameters
• Zero forcing in claw-free cubic graphs
• Maximum nullity and zero forcing of circulant graphs
• There's No Forcing a Least Upper Bound
• The Zero Forcing Number of Graphs
• The forcing number of graphs with given girth
• Propagation time for probabilistic zero forcing
• On the zero forcing number of some Cayley graphs
• Bounds for the Zero Forcing Number of Graphs with Large Girth
• A lower bound on the failed zero-forcing number of a graph
• On graphs maximizing the zero forcing number
• The zero forcing number of graphs with the matching number and the cyclomatic number
• Maximum nullity, zero forcing number and propagation time of -path graphs
• Bounding the total forcing number of graphs
• The zero (total) forcing number and covering number of trees
• On a conjecture of \textit{TxGraffiti}: relating zero forcing and vertex covers in graphs
• Zero forcing number and propagation time discrepancy of some graphs
• Zero forcing number and maximum nullity of general power graphs
• The extremal results for forcing problem of trees

This page was built for publication: A lower bound on the zero forcing number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801082)