On the nullity of graphs with pendent vertices

✍ Scribed by Shuchao Li

• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 188 KB
• Volume: 429
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2008.04.037

✦ Synopsis

The nullity of a graph G, denoted by η(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 η(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 n vertices.