Constructing fifteen infinite classes of nonregular bipartite integral graphs

Ligong Wang ; Cornelis Hoede

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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.

Détail

DOI : 10.37236/732

Classification : 05C50, 11D09, 11D41
Mots-clés : integral graphs, eigenvalues, adjacency matrix