Bounding the Forcing Number of a Graph

Abstract

The forcing number, denoted F(G), is an upper bound for the maximum nullity of all symmetric matrices with a sparsity pattern described by the simple graph G. Simple lower and upper bounds are δ ≤ F(G) where δ is the minimum degree and F (G) ≤ n − 1 where n is the order of the graph. This thesis provides improvements on the minimum degree lower bound in the case that G has girth of at least 5. In particular, it is shown that 2δ − 2 ≤ F (G) for graphs with girth of at least 5; this can be further improved when G has a small cut set. Further, this thesis also conjectures a lower bound on F(G) as a function of the girth, g, and δ.