Characterization of Graphs with Some Normalized Laplacian Eigenvalue Having Multiplicity

n-4

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n{-}4$$\end{document}

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

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n\ge 25$$\end{document}

with some normalized Laplacian eigenvalue

\rho \in (0,\frac{n-1}{n-2})

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\rho \in \big (0,\,\frac{n-1}{n-2}\big )$$\end{document}

having multiplicity

n-4

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n{-4}$$\end{document}

.

Keywords

Graph / Normalized Laplacian matrix / Multiplicity of eigenvalues / 05C50 / 15A18

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\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n-3$$\end{document}. 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\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n-3$$\end{document}. 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)

Rights & permissions

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature