Graphs with four distinct Laplacian eigenvalues (Q644702): Difference between revisions

Let \(G\) be a graph with the vertex set \(\{v_1,\ldots,v_n\}\). The adjacency matrix of \(G\) is an \(n\times n\) matrix \(A(G)\) whose \((i, j)\)-entry is 1 if \(v_i\) is adjacent to \(v_j\) and 0 otherwise. The matrix \(L(G) = D(G)-A(G)\) is called the Laplacian matrix of \(G\) where \(D(G)\) is the diagonal matrix whose \(i\)-the entry on the diagonal is the degree of \(v_i\). Graphs with few distinct adjacency (Laplacian) eigenvalues form an interesting class of graphs and possess nice combinatorial properties. Following \textit{E. R. van Dam} and \textit{W. H. Haemers} [``Graphs with constant \(\mu\) and \(\bar\mu\),'' Discrete Math. 182, No. 1-3, 293--307 (1998; Zbl 0901.05068)] who studied the nonregular graphs with three Laplacian eigenvalues, the authors investigate connected nonregular graphs with four distinct Laplacian eigenvalues. They characterize all such graphs which are bipartite, namely they prove that a connected bipartite graph \(G\) with \(n\geq5\) vertices has four distinct Laplacian eigenvalues if and only if \(G\) is one of {\parindent=6mm \begin{itemize}\item[1)]the incidence graph of a symmetric design, \item[2)]the graph obtained from the incidence graph of the Fano plane or its complement by joining one new vertex to all the vertices of one part, \item[3)]the graph obtained from the complete bipartite graph \(K_{n,n}\) by removing one edge, or \item[4)]\(K_{r, n-r}\) with \(1 < r < n/2\). \end{itemize}} Connected nonregular graphs with four distinct Laplacian eigenvalues with exactly one multiple eigenvalue are also classified.