Three Classes of Bipartite Integral Graphs

Ligong Wang and Hao Sun
Department of Applied Mathematics, School of Science,
Northwestern Polytechnical University,
Xi'an 710072,
P.R.China

Abstract    
A graph G is called integral if all the zeros of the characteristic polynomial P(G,x) are integers. Our purpose is to determine or to characterize which graphs are integral. This problem was posed by Harary and Schwenk in 1974. In general, the problem of characterizing integral graphs seems to be very difficult. Thus, it makes sense to restrict our investigations to some interesting families of graphs. So far, there are many results on some particular classes of integral graphs. In this paper, the bipartite graphs K_p,q(t), K_p(s),q(t) and K_p,qK_q,r are defined. We shall give their characteristic polynomials from the theory on matrices. We also obtain their sufficient and necessary conditions for the three classes of graphs to be integral. These results generalize some results of Balinska et al. The discovery of these integral graphs is a new contribution to the search of integral graphs.