Integral Laplacian graphs with a unique repeated Laplacian eigenvalue, I

Abstract

The set Si,n={0,1,2,…,n−1,n}\{i}{S}_{i,n}=\left\{0,1,2,\ldots ,n-1,n\right\}\setminus \left\{i\right\}, 1⩽i⩽n1\leqslant i\leqslant n, is called Laplacian realizable if there exists an undirected simple graph whose Laplacian spectrum is Si,n{S}_{i,n}. The existence of such graphs was established by Fallat et al. (On graphs whose Laplacian matrices have distinct integer eigenvalues, J. Graph Theory 50 (2005), 162–174). In this article, we consider graphs whose Laplacian spectra have the form S{i,j}nm={0,1,2,…,m−1,m,m,m+1,…,n−1,n}\{i,j},0<i<j⩽n,{S}_{{\left\{i,j\right\}}_{n}^{m}}=\left\{0,1,2,\ldots ,m-1,m,m,m+1,\ldots ,n-1,n\right\}\setminus \left\{i,j\right\},\hspace{1.0em}0\lt i\lt j\leqslant n, and completely describe those with m=n−1m=n-1 and m=nm=n. We also show close relations between graphs realizing Si,n{S}_{i,n} and S{i,j}nm{S}_{{\left\{i,j\right\}}_{n}^{m}} and discuss the so-called Sn,n{S}_{n,n}-conjecture and the corresponding conjecture for S{i,n}nm{S}_{{\left\{i,n\right\}}_{n}^{m}}.

Keywords

• laplacian integral graphs
• laplacian matrix
• laplacian spectrum
• integer eigenvalues
• 05c50
• 05c76
• 15a18