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

DOI10.1016/J.LAA.2021.07.024zbMATH Open1476.05128arXiv2012.11929OpenAlexW3191322565MaRDI QIDQ820993FDOQ820993

Fenglei Tian, Yiju Wang

Publication date: 29 September 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Let $G$ be a connected simple graph of order $n$. Let $h{o}_1(G)geqh{o}_2(G)geqcdotsgeqh{o}_{n-1}(G)>h{o}_n(G)=0$ be the eigenvalues of the normalized Laplacian matrix $mathcalL(G)$ of $G$. Denote by $m(h{o}_i)$ the multiplicity of the normalized Laplacian eigenvalue $h{o}_i$. Let $u(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(h{o}_1)=n-3$ ($ngeq6$) and $u(G)=2$. Moreover, we confirm that all the graphs with $m(h{o}_1)=n-3$ are determined by their normalized Laplacian spectra.

Full work available at URL: https://arxiv.org/abs/2012.11929

Recommendations

• Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity \(n - 3\)
• On the multiplicities of normalized Laplacian eigenvalues of graphs
• Independence number and the normalized Laplacian eigenvalue one
• On graphs with three or four distinct normalized Laplacian eigenvalues
• Normalized Laplacian eigenvalues with chromatic number and independence number of graphs

zbMATH Keywords

spectral graph theoryeigenvalue multiplicitynormalised Laplacian spectrum

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Title not available (Why is that?)
• On the multiplicities of normalized Laplacian eigenvalues of graphs
• Bounds on normalized Laplacian eigenvalues of graphs
• Graphs whose normalized Laplacian has three eigenvalues
• The largest normalized Laplacian spectral radius of non-bipartite graphs
• On Graphs with Three or Four Distinct Normalized Laplacian Eigenvalues
• Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity \(n - 3\)
• On the second largest normalized Laplacian eigenvalue of graphs
• Normalized Laplacian spectrum of complete multipartite graphs
• Trees with 4 or 5 distinct normalized Laplacian eigenvalues

Cited In (4)

• Laplacian eigenvalue distribution of a graph with given independence number
• Graphs whose normalized Laplacian has three eigenvalues
• Independence number and the normalized Laplacian eigenvalue one
• The characterization of graphs with eigenvalue -1 of multiplicity n-4 or n-5

This page was built for publication: Full characterization of graphs having certain normalized Laplacian eigenvalue of multiplicity \(n-3\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820993)