Constructing fifteen infinite classes of nonregular
bipartite integral graphs∗
Ligong Wang1,†and Cornelis Hoede2
1Department of Applied Mathematics, School of Science,
Northwestern Polytechnical University, Xi’an, Shaanxi 710072, P. R. China.
ligongwangnpu@yahoo.com.cn
2Department of Applied Mathematics,
Faculty of Electrical Engineering, Mathematics and Computer Science,
University of Twente, P.O. Box 217, 7500AE Enschede, The Netherlands.
hoede@math.utwente.nl
Submitted: Oct 5, 2007; Accepted: Dec 16, 2007; Published: Jan 1, 2008
Mathematics Subject Classifications: 05C50, 11D09, 11D41
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, t), S4(m, n, p, q),
S5(m, n), S6(m, n, t), S8(m, n), S9(m, n, p, q), S10(n), S13(m, n), S17(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´nska and Simi´c, 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.
1 Introduction
We use Gto denote a simple graph with vertex set V(G) = {v1, v2, . . . , vn}and edge set
E(G). The adjacency matrix A=A(G) = [aij ] of Gis an n×nsymmetric matrix of 0’s
∗Supported by National Science Foundation of China and Natural Science Basic Research Plan in
Shaanxi Province of China.
†Corresponding author.
the electronic journal of combinatorics 15 (2008), #R8 1
and 1’s with aij = 1 if and only if viand vjare joined by an edge. The characteristic
polynomial of Gis the polynomial P(G) = P(G, x) = det(xIn−A), where and in the
sequel Inalways denotes the n×nidentity matrix. The spectrum of A(G) is also called
the spectrum of Gand denoted by Spec(G) ([5]).
A graph Gis called integral if all eigenvalues of the characteristic polynomial P(G, x)
of Gare integers. The research on integral graphs was initiated by Harary and Schwenk
[7]. 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 for some particular classes of integral graphs [1]. For all
other facts or terminology on graph spectra, see [5].
In [9] we successfully constructed integral trees of diameters 4 and 6 by identifying the
centers of two trees. In [10, 11] we investigated the structures of some classes of graphs and
deduce their characteristic polynomials by spectral graph theory. Integral graphs in these
classes were given by using number theory and computer search. In this paper, a new
method of constructing fifteen infinite classes of integral graphs is presented. In getting
the results we proceed as follows: firstly, we give the construction of the (infinite) families
of new graphs from the 15 finite classes of integral graphs identified by Bali´nska and
Simi´c [2], then calculate their characteristic polynomials (Theorem 3.2) by using matrix
theory, and then, by making use of number theory (Diophantine equations) and computer
search, we obtain fifteen infinite classes of integral graphs in these classes. These classes
are connected nonregular and bipartite graphs except for several disconnected graphs for
which one or several of their parameters are taken zero. Finally, we propose several open
problems for further study.
2 Some facts in matrix theory and number theory
In this section, we shall give a useful property of matrices and some facts in number
theory.
First of all, we give the following notations. All other notations and terminology on
matrices can be found in [6].
(1) Rdenotes the set of real numbers.
(2) Rm×ndenotes the set of m×nmatrices whose entries are in R.
(3) ATdenotes the transpose of the matrix A.
(4) Jm×nand 0m×ndenotes the m×nall 1 and all 0 matrix, respectively.
Lemma 2.1. ([6], page 181) Let A=A0A1
A1A0, where Ak∈Rr×r,k= 0,1. Then the
eigenvalues of Aare those of A0+A1together with those of A0−A1.
Secondly, we shall give some facts in number theory. All other notations and termi-
nology on number theory can be found in [4, 8].
Let dbe a positive integer but not a perfect square, let m6= 0 be an integer. We shall
study the Diophantine equation
x2−dy2=m. (1)
the electronic journal of combinatorics 15 (2008), #R8 2
If x1,y1is a solution of (1), for convenience, then x1+y1√dis also called a solution
of Eq.(1). Let s+t√dbe any solution of the Pell equation
x2−dy2= 1.(2)
Clearly, (x1+y1√d)(s+t√d) = x1s+y1td+(y1s+x1t)√dis also a solution of Eq.(1). This
solution and x1+y1√dare called associate. If two solutions x1+y1√dand x2+y2√dof
Eq.(1) are associate, then we denote them by x1+y1√d∼x2+y2√d. It is easy to verify
that the associate relation ∼is an equivalence relation. Hence, if Eq.(1) has solutions,
then all the solutions can be classified by the associate relation. Any two solutions in the
same associate class are associate each other, any two solutions not in the same class are
not associate.
The following Lemmas 2.2, 2.3, 2.4 and 2.5 can be found in [4].
Lemma 2.2. A necessary and sufficient condition for two solutions x1+y1√dand x2+
y2√dof Eq.(1) (mfixed) to be in the same associate class Kis that
x1x2−dy1y2≡0(mod|m|)and y1x2−x1y2≡0(mod|m|).
Let x1+y1√dbe any solution of Eq.(1). By Lemma 2.2, we see that −(x1+y1√d)∼
x1+y1√d,−(x1−y1√d)∼x1−y1√d. Let Kand K′be two associate classes of solutions
of Eq. (1) such that for any solution x+y√d∈K, it follows x−y√d∈K′. Then also the
converse is true. Hence, Kand K′are called conjugate classes. If K=K′, then this class
is called an ambiguous class. Let u0+v0√dbe the fundamental solution of the associate
class K,i.e. v0is positive and has the smallest value in the class K. If the class Kis
ambiguous, we can assume that u0≥0.
Lemma 2.3. Let Kbe any associate class of solutions of Eq.(1), and let u0+v0√dbe the
fundamental solution of the associate class K. Let x0+y0√dbe the fundamental solution
of the Pell equation (2). Then
0≤v0≤
y0√m
√2(x0+1) ,if m > 0,
y0√−m
√2(x0−1) ,if m < 0.(3)
0≤ |u0| ≤
q1
2(x0+ 1)m, if m > 0,
q1
2(x0−1)(−m),if m < 0.(4)
Lemma 2.4.
(1) Let dbe a positive integer but not a perfect square, m6= 0, and let mbe an integer.
Then there are only finitely many associate classes for Eq.(1), and the fundamental
solutions of all these classes can be found from (3) and (4) by a finite procedure.
the electronic journal of combinatorics 15 (2008), #R8 3
(2) Let Kbe an associate class of solutions of Eq. (1), and let u0+v0√dbe the fun-
damental solution of the associate class K. Then all solutions of the class Kare
given by
x+y√d=±(u0+v0√d)(x0+y0√d)n,
where nis an integer, and x0+y0√dis the fundamental solution of Eq.(2).
(3) If u0and v0satisfy (3) and (4) but are not solutions of Eq.(1), then there is no
solution for Eq.(1).
Lemma 2.5. Let d(>1) be a positive integer that is not a perfect square. Then there
exist solutions for the Pell equation (2), and all the positive integral solutions xk, ykof
Eq.(2) are given by
xk+yk√d=εk, k = 1,2, . . . , (5)
where ε=x0+y0√dis the fundamental solution of Eq.(2). Put ε=x0−y0√d. Then we
have εε = 1 and
xk=εk+εk
2, yk=εk−εk
2√d, k = 1,2, . . . . (6)
The following Lemmas 2.6, 2.9, 2.11 and Lemmas 2.7, 2.8 can be found in [8] and [4],
respectively.
Lemma 2.6. Let u, v be the fundamental solution of Eq.(2), where d(>1) is a positive
integer but not a perfect square. Then the Pell equation
x2−dy2=−1 (7)
has solutions if and only if there exist positive integer solutions sand tfor the equations
s2+dt2=u, 2st =v,
such that moreover sand tare the fundamental solution of Eq.(7).
Lemma 2.7. Suppose the Pell equation (7) is solvable. Let ρ=x0+y0√dbe the fun-
damental solution of Eq.(7), where d(>1) is a positive integer but not a perfect square.
Then the following holds.
(1) All positive integral solutions xk, ykof Eq.(7) are given by
xk+yk√d=ρk, k = 1,3,5, . . . . (8)
(2) All positive integral solutions xk, ykof Eq. (2) are given by relation (8),k= 2,4, . . . .
(3) Let ρ=x0−y0√d, then ρρ =−1, and the solutions xk,ykin (1) and (2) can be
given by
xk=ρk+ρk
2, yk=ρk−ρk
2√d, k = 1,2, . . . . (9)
the electronic journal of combinatorics 15 (2008), #R8 4
Lemma 2.8.
(1) If there is a solution for Eq.(1), where m6= 0 is integer and d(>1) is a positive
integer but not a perfect square, then Eq.(1) has infinitely many solutions.
(2) Let x1, y1be the fundamental solution of the Diophantine equation
x2−dy2= 4,(10)
where d(>1) is a positive integer but not a perfect square. Then all positive integral
solutions xk, ykof Eq.(10) are given by
xk+yk√d
2= (x1+y1√d
2)k, k = 1,2, . . . . (11)
In the following symbol (a, b) = ddenotes the greatest common divisor dof integers
a, b, while a|b(a∤b) means that adivides b(adoes not divide b) .
Lemma 2.9. Let mbe a positive integer. If 2∤mor 4|m, then there exist positive integral
solutions for the Diophantine equation
x2−y2=m. (12)
Remark 2.10. We can give a method for finding the solutions of Eq.(12). Suppose that
m=m1m2. Let x−y=m1,x+y=m2and 2|(m1+m2). Then the solutions of Eq.
(12) can be found easily (see [8]).
Lemma 2.11. If x > 0,y > 0,z > 0,(x, y) = 1 and 2|y, then all positive integral
solutions of the Diophantine equation x2+y2=z2are given by
x=r2−s2, y = 2rs, z =r2+s2,
where (r, s) = 1, r > s > 0and 2∤r+s.
3 The characteristic polynomials of some classes of
graphs
In this section, we investigate the structures of the nonregular bipartite integral graphs
in [2]. Fifteen new classes of larger graphs are constructed based on the structures of 15
ones of the 21 smaller integral graphs in Figures 4 and 5 of [2].
Theorem 3.1. ( [2] ) The graphs in Figures 1 and 2 are nonregular bipartite integral
graphs with maximum degree four. (The graphs in Figure 1 are integral graphs with number
of vertices up to 16.)
the electronic journal of combinatorics 15 (2008), #R8 5
