A lower bound on the zero forcing number

DOI10.1016/J.DAM.2018.04.015zbMATH Open1398.05083DBLPjournals/dam/DavilaKS18arXiv1611.06557OpenAlexW2795526790WikidataQ57955244 ScholiaQ57955244MaRDI QIDQ1801082FDOQ1801082

Sudeep Stephen, Thomas Kalinowski, Randy Davila

Publication date: 26 October 2018

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

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.

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

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

zbMATH Keywords

zero forcingpropagation in graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Zero forcing sets and the minimum rank of graphs
• Graph Theory
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph
• Zero forcing parameters and minimum rank problems
• Some bounds on the zero forcing number of a graph
• Proof of a conjecture on the zero forcing number of a graph
• Extremal values and bounds for the zero forcing number
• 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\)

Cited In (22)

• Propagation time for probabilistic zero forcing
• Blocking zero forcing processes in Cartesian products of graphs
• On the zero forcing number of a graph involving some classical parameters
• There's No Forcing a Least Upper Bound
• The zero forcing number of graphs with the matching number and the cyclomatic number
• Total forcing versus total domination in cubic graphs
• The Zero Forcing Number of Graphs
• On the semitotal forcing number of a graph
• Zero forcing versus domination in cubic graphs
• Zero forcing in claw-free cubic 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
• On the zero blocking number of rectangular, cylindrical, and Möbius grids
• On graphs maximizing the zero forcing number
• Title not available (Why is that?)
• Note on forcing problem of trees
• Maximum nullity and zero forcing of circulant graphs
• On the zero forcing number and spectral radius of graphs
• On the total forcing number of a graph
• Bounds on the connected forcing number of a graph
• A lower bound on the failed zero-forcing number of a graph

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)