\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Ligong Wang and Cornelis Hoede}
%
%
\medskip
\noindent
%
%
{\bf Constructing Fifteen Infinite Classes of Nonregular Bipartite Integral Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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{\'{n}}ska and Simi{\'{c}}, Discrete Math. {\bf 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.

\bye

.
