Zero Forcing And Maximum Nullity Of Graphs

Abstract

The zero forcing game on a simple, undirected graph G is based on the so-called color change rule which can be stated as if some vertices on G are colored black while others are white and vertex v is a black vertex with exactly one white neighbor u, then change the color of vertex u to be black vertex. A zero forcing set is a subset of black vertices such that if we apply the color change rule, we have all vertices on G are black vertices. A new parameter so-called zero forcing number Z(G) which is the minimum size of a zero forcing set among all zero forcing sets of G. The maximum nullity M(G) of a graph G is to determine the largest nullity over all symmetric matrices whose (i, j)th entry, i 6= j, is nonzero when {i, j} are connected with an edge in G and is zero otherwise. The zero forcing number Z(G) is helpful to study the M(G). Indeed, it is shown that Z(G) is upper bound on M(G). We conclude this thesis by studying the maximum nullity of symmetric matrices that represent of trees with a fixed number of negative eigenvalues.