Constructing fifteen infinite classes of nonregular bipartite integral graphs

Ligong Wang, Cornelis Hoede

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs S1(t) = K1,t, S2(n, t), S3;(m, n, p, q), S4(m, n, p, q), S5(m, n), S6(m, n, t), S8(m, n), S 9(m, n, p, q), S10(n), S13{m, n), S 17(m, n, p, q), S18(n, p, q, t), S19(m, n, p, t), S20(n, p, q) and S21 (m, t) are defined. We construct the fifteen classes of larger graphs from the known 15 smaller integral graphs S1 - S6, S8 - S10, S13, S17 - S21 (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.

Original languageEnglish
Article numberR8
JournalElectronic Journal of Combinatorics
Volume15
Issue number1 R
DOIs
StatePublished - 1 Jan 2008

Fingerprint

Dive into the research topics of 'Constructing fifteen infinite classes of nonregular bipartite integral graphs'. Together they form a unique fingerprint.

Cite this