Maximum generic nullity of a graph

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n x n matrices A whose (i, j)th entry (for i not equal j) is nonzero whenever (i, j) is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree. (C) 2007 Elsevier Inc. All rights reserved.