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.