Two classes of integral regular graphs

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) denote the diagonal matrix of the vertex degrees of G. Let K_n,n+1 ≡ K_n+1,nand K_1,p[(p-1)K _p] denote the (n+1)-regular graph with 4n+2 vertices and the p-regular graph with p² + l vertices, respectively. In this paper, we shall give the spectra and characteristic polynomials of K_n,n+1 ≡ 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₂ + 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.