ELA, Volume 16, pp. 60-67, January 2007, abstract.

On the Nullity of Graphs

Bo Cheng and Bolian Liu
 
The nullity of a graph G, denoted by \eta(G), is the
multiplicity of the eigenvalue zero in its spectrum. 
It is known that \eta(G) <= n-2 if G is a simple graph 
on n vertices and G is not isomorphic to nK_1. In this 
paper, we characterize the extremal graphs attaining 
the upper bound n-2 and the second upper bound n-3. 
The maximum nullity of simple graphs with n vertices
and e edges, M(n,e), is also discussed. We obtain an 
upper bound of M(n,e), and characterize n and e for 
which the upper bound is achieved.