Theory and Applications of Graphs Theory and Applications of Graphs

Abstract

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 and δ ; this conjecture is proved in a few cases and numerical evidence is provided.