The classification of graphs on eight vertices with coinciding zero forcing number and maximum nullity

Abstract

This article studies the minimum rank of a (simple, undirected) graph, which is the minimum rank among all matrices in a space determined by the graph. It determines the exact set of graphs on eight vertices for which the nullity of a minimum rank matrix does not coincide with a bound determined by the zero forcing number of a graph. Although the goal was to determine which eight-vertex graphs satisfy maximum nullity equal to the zero forcing number, it also establishes several additional methods to assist in the computation of minimum rank for general graphs.