On the nullity of graphs with pendent vertices

The nullity of a graph G, denoted by eta(G), is the multiplicity of the eigenvalue zero in its spectrum. Cheng and Liu [B. Cheng, B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007) 60-67] characterized the extremal graphs attaining the upper bound n - 2 and the second upper bound n - 3. In this paper, as the continuance of it, we determine the extremal graphs with pendent vertices achieving the third upper bound n - 4 and fourth upper bound n - 5. We then proceed recursively to construct all graphs with pendent vertices which satisfy eta(G) > 0. Our results provide a unified approach to determine n-vertex unicyclic (respectively, bicyclic and tricyclic) graphs which achieve the maximal and second maximal nullity and characterize n-vertex extremal trees attaining the second and third maximal nullity. As a consequence we, respectively, determine the nullity sets of trees. unicyclic graphs, bicyclic graphs and tricyclic graphs on it vertices. (C) 2008 Elsevier Inc. All rights reserved.