Bounds for the Zero Forcing Number of Graphs with Large Girth

The zero-forcing number, Z(G) is an upper bound for the maximum nullity of all symmetric matrices with a sparsity pattern described by the graph. A simple lower bound is δ ≤ Z(G) where δ is the minimum degree. An improvement of this bound is provided in the case that G has girth of at least 5. In particular, it is shown that 2δ − 2 ≤ Z(G) for graphs with girth of at least 5; this can be further improved when G has a small cut set. Lastly, a conjecture is made regarding a lower bound for Z(G) as a function of the girth, g, and δ; this conjecture is proved in a few cases and numerical evidence is provided.

Abstract licence: CC BY

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.