A classification of graphs of order $ n $ with at least $ n-4 $ Laplacian eigenvalues greater than $ n-1 $

Yifan Liu; Jinxing Zhao; Yifan Liu; Jinxing Zhao

doi:10.3934/math.20261185

AIMS Mathematics

2026, Volume 11, Issue 9: 29875-29887. doi: 10.3934/math.20261185

Previous Article Next Article

Research article

A classification of graphs of order $ n $ with at least $ n-4 $ Laplacian eigenvalues greater than $ n-1 $

Yifan Liu ,
Jinxing Zhao ^,

School of Mathematical Sciences, Inner Mongolia University, Hohhot, China

Received: 13 May 2026 Revised: 29 August 2026 Accepted: 02 September 2026 Published: 15 September 2026
MSC : 05C50

Let $ G $ be a connected graph of order $ n $ and $ m_G(I) $ be the number of Laplacian eigenvalues of $ G $ in an interval $ I $. It is well known that the Laplacian eigenvalues of $ G $ are all in the interval $ [0, n] $. Some attention has been paid to the distribution of Laplacian eigenvalues in a subinterval of $ [0, n] $ of length $ 1 $. In 2022, Ahanjideh et al. ^[1] gave a classification for graphs with at least $ n-2 $ Laplacian eigenvalues in $ [0, 1] $. In 2020, Wang et al. ^[2] proved that $ m_G (n -1, n] \leq \kappa $ and $ m_G (n -1, n] \leq \chi-1 $, where $ \kappa $ and $ \chi $ are the vertex-connectivity and the chromatic number of $ G $. Based on the above bounds for $ m_G (n -1, n] $ together with some other bounds for $ m_G[0, 1) $, we give a classification for connected graphs of order $ n $ with $ m_G (n -1, n]\geq n-4 $.
- distribution of Laplacian eigenvalue,
- multiplicity of eigenvalues,
- Laplacian matrix
Citation: Yifan Liu, Jinxing Zhao. A classification of graphs of order $ n $ with at least $ n-4 $ Laplacian eigenvalues greater than $ n-1 $[J]. AIMS Mathematics, 2026, 11(9): 29875-29887. doi: 10.3934/math.20261185

Related Papers:

Abstract

Let $ G $ be a connected graph of order $ n $ and $ m_G(I) $ be the number of Laplacian eigenvalues of $ G $ in an interval $ I $. It is well known that the Laplacian eigenvalues of $ G $ are all in the interval $ [0, n] $. Some attention has been paid to the distribution of Laplacian eigenvalues in a subinterval of $ [0, n] $ of length $ 1 $. In 2022, Ahanjideh et al. ^[1] gave a classification for graphs with at least $ n-2 $ Laplacian eigenvalues in $ [0, 1] $. In 2020, Wang et al. ^[2] proved that $ m_G (n -1, n] \leq \kappa $ and $ m_G (n -1, n] \leq \chi-1 $, where $ \kappa $ and $ \chi $ are the vertex-connectivity and the chromatic number of $ G $. Based on the above bounds for $ m_G (n -1, n] $ together with some other bounds for $ m_G[0, 1) $, we give a classification for connected graphs of order $ n $ with $ m_G (n -1, n]\geq n-4 $.

References

[1]	M. Ahanjideh, S. Akbari, M. H. Fakharan, V. Trevisan, Laplacian eigenvalue distribution and graph parameters, Linear Algebra Appl., 632 (2022), 1–14. https://doi.org/10.1016/j.laa.2021.09.012 doi: 10.1016/j.laa.2021.09.012
[2]	L. Wang, C. Yan, X. Fang, X. Geng, F. Tian, Vertex-connectivity, chromatic number, domination number, maximum degree and Laplacian eigenvalue distribution, Linear Algebra Appl., 607 (2020), 307–318. https://doi.org/10.1016/j.laa.2020.08.011 doi: 10.1016/j.laa.2020.08.011
[3]	I. Faria, Permanental roots and the star degree of a graph, Linear Algebra Appl., 64 (1985), 255–265. https://doi.org/10.1016/0024-3795(85)90281-2 doi: 10.1016/0024-3795(85)90281-2
[4]	R. Grone, R. Merris, V. S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl., 11 (1990), 218–238. https://doi.org/10.1137/0611016 doi: 10.1137/0611016
[5]	R. Merris, The number of eigenvalues greater than two in the Laplacian spectrum of a graph, Port. Math., 48 (1991), 345–349.
[6]	J. M. Guo, S. W. Tan, A relation between the matching number and Laplacian spectrum of a graph, Linear Algebra Appl., 325 (2001), 71–74. https://doi.org/10.1016/S0024-3795(00)00333-5 doi: 10.1016/S0024-3795(00)00333-5
[7]	J. M. Guo, X. L. Wu, J. M. Zhang, K. F. Fang, On the distribution of Laplacian eigenvalues of a graph, Acta Math. Sinica, 27 (2011), 2259–2268. https://doi.org/10.1007/s10114-011-8624-y doi: 10.1007/s10114-011-8624-y
[8]	S. T. Hedetniemi, D. P. Jacobs, V. Trevisan, Domination number and Laplacian eigenvalue distribution, European J. Combin., 53 (2016), 66–71. https://doi.org/10.1016/j.ejc.2015.11.005 doi: 10.1016/j.ejc.2015.11.005
[9]	D. P. Jacobs, E. R. Oliveira, V. Trevisan, Most Laplacian eigenvalues of a tree are small, J. Comb. Theory, Ser. B, 146 (2021), 1–33. https://doi.org/10.1016/j.jctb.2020.07.003 doi: 10.1016/j.jctb.2020.07.003
[10]	C. Sin, On the number of Laplacian eigenvalues of trees less than the average degree, Discrete Math., 343 (2020), 111986. https://doi.org/10.1016/j.disc.2020.111986 doi: 10.1016/j.disc.2020.111986
[11]	V. Trevisan, J. B. Carvalho, R. R. Del Vecchio, C. T. M. Vinagre, Laplacian energy of diameter $3$ trees, Appl. Math. Lett., 24 (2011), 918–923. https://doi.org/10.1016/j.aml.2010.12.050 doi: 10.1016/j.aml.2010.12.050
[12]	L. Xu, B. Zhou, Proof of a conjecture on distribution of Laplacian eigenvalues and diameter, and beyond, Linear Algebra Appl., 678 (2023), 92–106. https://doi.org/10.1016/j.laa.2023.08.013 doi: 10.1016/j.laa.2023.08.013
[13]	A. El-Mesady, Y. S. Hamed, H. Shabana, On the decomposition of circulant graphs using algorithmic approaches, Alex. Eng. J., 61 (2022), 8263–8275. https://doi.org/10.1016/j.aej.2022.01.049 doi: 10.1016/j.aej.2022.01.049
[14]	B. Mohar, The Laplacian spectrum of graphs, In: Graph theory, combinatorics, and applications, Wiley, 1991,871–898.
[15]	C. Godsil, G. Royle, Algebraic graph theory, New York: Springer, 2001. https://doi.org/10.1007/978-1-4613-0163-9
[16]	A. E. Brouwer, W. H. Haemers, Spectra of graphs, New York: Springer, 2012. https://doi.org/10.1007/978-1-4614-1939-6
[17]	M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J., 23 (1973), 298–305. https://doi.org/10.21136/CMJ.1973.101168 doi: 10.21136/CMJ.1973.101168

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)