Dissertation

2019

#### Degree Name

Doctor of Philosophy

Mathematics

Mathematics

Leslie Hogben

#### Abstract

The maximum nullity of a simple graph $G$ over a field $\mathcal{F}$ is the

maximum nullity over all symmetric matrices over $\mathcal{F}$ whose $ij$th

entry (where $i \neq j$ ) is nonzero if and only if $ij$ is an edge in $G$ and

is zero otherwise. The zero forcing number of a graph is the minimum

cardinality over all zero forcing sets. It is known that the zero forcing number of a graph

is an upper bound for the maximum nullity of the graph (see \cite{MR2388646}).

In this dissertation, we search for characteristics of a graph that guarantee

the maximum nullity of the graph and the zero forcing number of the graph are

the same by studying a variety of graph parameters which bound the maximum nullity

of a graph below. Graph parameters that are considered are a Colin de Verdi\'ere type parameter and the vertex connectivity. We also use matrices, such as a divisor matrix of a graph and an equitable partition of the adjacency matrix of a graph, to establish a lower bound for the nullity of the graph's adjacency matrix. Last, we introduce a new graph parameter and show that it has the same value as the nullity of the graph's adjacency matrix, which is a lower bound for the maximum nullity of a graph.

Derek Dwight Young

en

application/pdf

46 pages

COinS