Characterization of Graphs with Some Normalized Laplacian Eigenvalue Having Multiplicity $n{-}4$

Abstract

The spectrum of the normalized Laplacian matrix of a graph provides a lot of structural information of the graph, and it has applications in numerous areas and in different guises. In this paper, we completely characterize all connected graphs of order $n\ge 25$ with some normalized Laplacian eigenvalue $\rho \in \big (0,\,\frac{n-1}{n-2}\big )$ having multiplicity $n{-4}$.

Keywords

Graph / Normalized Laplacian matrix / Multiplicity of eigenvalues

References

[1] Bondy JA, Murty USR. Graph theory with applications. 1976 New York: MacMillan

[2] Berman A, Chen DM, Chen ZB, Liang WZ, Zhang XD. A family of graphs that are determined by their normalized Laplacian spectra. Linear Algebra Appl.. 2018, 548 66-76

[3] Cavers, M.: The normalized Laplacian matrix and general Randić index of graphs, PhD dissertation, University of Regina, (2010)

[4] Chang GJ, Huang LH, Yeh HG. A characterization of graphs with rank 4. Linear Algebra Appl.. 2011, 434 1793-1798

[5] Chung, F.K.: Spectral graph theory. AMS, Providence (1997)

[6] Das KC, Sun S. Extremal graph on normalized Laplacian spectral radius and energy, Elect. Jour. Linear. Algebra. 2016, 29 237-253

[7] Jost J, Mulas R, Münch F. Spectral gap of the largest eigenvalue of the normalized graph Laplacian. Commun. Math. Stat.. 2022, 10 371-381

[8] Li J, Guo J-M, Shiu WC. Bounds on normalized Laplacian eigenvalues of graphs. J. Ineq. Appl.. 2014, 316 1-8

[9] Milovanović EI, Matejić MM, Milovanović IŽ. On the normalized Laplacian spectral radius, Laplacian incidence energy and Kemeny’s constant. Linear Algebra Appl.. 2019, 582 181-196

[10] Oboudi MR. Characterization of graphs with exactly two non-negative eigenvalues. Ars Math. Contemp.. 2017, 12 271-286

[11] Radziszowski, S.P.: Small Ramsey numbers, Electron. J. Combin. DS1.16 (2021)

[12] Schur I. Über eine Klasse von Mittelbildungen mit Anwendungen auf die Determinantentheorie. Sitzungsber. Berl. Math. Ges.. 1923, 22 9-20

[13] Sun S, Das KC. Normalized Laplacian eigenvalues with chromatic number and independence number of graphs. Linear Multi. Algebra. 2020, 68 1 63-80

[14] Sun S, Das KC. On the second largest normalized Laplacian eigenvalue of graphs. Appl. Math. Comput.. 2019, 348 531-541

[15] Sun S, Das KC. On the multiplicities of normalized Laplacian eigenvalues of graphs. Linear Algebra Appl.. 2021, 609 365-385

[16] Tograsev A. Graphs with exactly two negative eigenvalues. Math. Nachr.. 1985, 122 135-140

[17] Tian F, Wong D, Wang S. Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity $n-3$. Linear Algebra Appl.. 2020, 606 127-143

[18] Tian F, Wang Y. Full characterization of graphs having certain normalized Laplacian eigenvalue of multiplicity $n-3$. Linear Algebra Appl.. 2021, 630 69-83

[19] van Dam ER, Omidi GR. Graphs whose normalized Laplacian has three eigenvalues. Linear Algebra Appl.. 2011, 435 2560-2569

Funding

National Natural Science Foundation of China(11901525)