On the nullity of a graph with cut-points

• Published in: Linear algebra and its applications 2012, Vol.436 (1), p.135-142
• Main Authors: Gong, Shi-Cai, Xu, Guang-Hui
• Format: Article
• Language: English
• Subjects: Adjacency matrix; Algebra; Combinatorics; Combinatorics. Ordered structures; Cut-point; Exact sciences and technology; Graph theory; Line graph; Linear and multilinear algebra, matrix theory; Matching; Mathematics; Nullity; Sciences and techniques of general use; Singularity
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2011.06.039

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 C k and L k the set of all connected graphs with k induced cycles and the set of line graphs of all graphs in C k , 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 L 0 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 ∈ C k and η ( L ( G ) ) = k + 1 , and the nullity set of L k is { 0 , 1 , … , k , k + 1 } for any given k, where L ( G ) denotes the line graph of the graph G.