Constructing Fifteen Infinite Classes of Nonregular Bipartite Integral Graphs

Source abstract

A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs $S_1(t)=K_{1,t}$, $S_2(n,t)$, $S_3(m,n,t)$, $S_4(m,n,p,q)$, $S_5(m,n)$, $S_6(m,n,t)$, $S_8(m,n)$, $S_9(m,n,p,q)$, $S_{10}(n)$, $S_{13}(m,n)$, $S_{17}(m, n, p, q)$, $S_{18}(n,p,q,t)$, $S_{19}(m,n,p,t)$, $S_{20}(n,p,q)$ and $S_{21}(m,t)$ are defined. We construct the fifteen classes of larger graphs from the known 15 smaller integral graphs $S_1-S_6$, $S_8-S_{10}$, $S_{13}$, $S_{17}-S_{21}$ (see also Figures 4 and 5, Balińska and Simić, Discrete Math. 236(2001) 13-24). These classes consist of nonregular and bipartite graphs. Their spectra and characteristic polynomials are obtained from matrix theory. We obtain their integral property by using number theory and computer search. All these classes are infinite. They are different from those in the literature. It is proved that the problem of finding such integral graphs is equivalent to solving Diophantine equations. We believe that it is useful for constructing other integral graphs. The discovery of these integral graphs is a new contribution to the search of integral graphs. Finally, we propose several open problems for further study.