Constructing Fifteen Infinite Classes of Nonregular Bipartite Integral Graphs 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_1S_6, S_8S_10, S_13, S_17S_21 (see also Figures 4 and 5, Balinska and Simic, Discrete Math.  236 (2001) 1324). 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.

On the Computational Complexity of Finding Bipartite Graphs with a Small Number of Short Cycles and Large Girth The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good lowdensity paritycheck (LDPC) codes. In this paper, we prove that for a given set of integers alpha, beta, and gamma, and degree sequences pi and pixe2x80x99, the problem of determining whether there exists a simple bipartite graph with degree sequences (pi, piu0027) that has at most alpha (beta and gamma) cycles of length four (six and eight, respectively) is NPcomplete. This is proved by a twostep polynomialtime reduction from the 3Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence pi, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is pi and has a girth of at least six.