Full characterization of graphs having certain normalized Laplacian eigenvalue of multiplicity n-3

2020/12/22 by Tian, Fenglei, Wang, Yiju
#05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2012.11929

Abstract

Let G be a connected simple graph of order n. Let ρ₁(G)≥ ρ₂(G)≥ ⋯ ≥ ρ_n-1(G)> ρ_n(G)=0 be the eigenvalues of the normalized Laplacian matrix L(G) of G. Denote by m(ρ_i) the multiplicity of the normalized Laplacian eigenvalue ρ_i. Let ν(G) be the independence number of G. In this paper, we give a full characterization of graphs with some normalized Laplacian eigenvalue of multiplicity n-3, which answers a remaining problem in [S. Sun, K.C. Das, On the multiplicities of normalized Laplacian eigenvalues of graphs, Linear Algebra Appl. 609 (2021) 365-385], i.e., there is no graph with m(ρ₁)=n-3 (n≥ 6) and ν(G)=2. Moreover, we confirm that all the graphs with m(ρ₁)=n-3 are determined by their normalized Laplacian spectra.

Related

• On graphs with some normalized Laplacian eigenvalue of extremal multiplicity
• Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity n-3
• On graphs with three or four distinct normalized Laplacian eigenvalues
• The full chracterazation of the graphs with a L-eigenvalue of multiplicity n-3
• Remarks on Bounds of Normalized Laplacian Eigenvalues of Graphs