Techniques for determining equality of the maximum nullity and the zero forcing number of a graph

Thumbnail Image
Date
2019-01-01
Authors
Young, Derek
Major Professor
Advisor
Leslie Hogben
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Department
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.

Comments
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright
Wed May 01 00:00:00 UTC 2019