On the nullity of a graph with cut-points

Linear Algebra Appl. 2012 Jan 1;436(1):135-142. doi: 10.1016/j.laa.2011.06.039.

Abstract

Let G be a simple graph of order n and A(G) be its adjacency matrix. The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in the spectrum of A(G). Denote by Ck and Lk the set of all connected graphs with k induced cycles and the set of line graphs of all graphs in Ck, respectively. In 1998, Sciriha [I. Sciriha, On singular line graphs of trees, Congr. Numer. 135 (1998) 73-91] show that the order of every tree whose line graph is singular is even. Then Gutman and Sciriha [I. Gutman, I. Sciriha, On the nullity of line graphs of trees, Discrete Math. 232 (2001) 35-45] show that the nullity set of L0 is {0,1}. In this paper, we investigate the nullity of graphs with cut-points and deduce some concise formulas. Then we generalize Scirihas' result, showing that the order of every graph G is even if such a graph G satisfies that G∈Ck and η(L(G))=k+1, and the nullity set of Lk is {0,1,…,k,k+1} for any given k, where L(G) denotes the line graph of the graph G.