Two Classes of Integral Regular Graphs

Abstract

A graph $G$ is called integral or Laplacian integral if all the eigenvalues of the adjacency matrix $A(G)$ or the Laplacian matrix $Lap(G)=D(G)–A(G)$ of $G$ are integers, where $D(G)$ denotes the diagonal matrix of the vertex degrees of $G$. Let $K_{n,n+1}\equiv K_{n+1,n}$ and $K_{1,p}[(p-1)K_p]$ denote the $(n+1)$-regular graph with $4n+2$ vertices and the $p$-regular graph with $p^2+1$ vertices, respectively. In this paper, we shall give the spectra and characteristic polynomials of $K_{n,n+1}\equiv K_{n+1,n}$ and $K_{1,p}[(p-1)K_p]$ from the theory on matrices. We derive the characteristic polynomials for their complement graphs, their line graphs, the complement graphs of their line graphs, and the line graphs of their complement graphs. We also obtain the numbers of spanning trees for such graphs. When $p=n^2+n+1$, these graphs are not only integral but also Laplacian integral. The discovery of these integral graphs is a new contribution to the search of integral graphs.