Informatica 30 (2006) 295-299 295
The Spectra of Knödel Graphs
Hovhannes A. Harutyunyan and Calin D. Morosan
Department of Computer Science
1455 de Maisonneuve Blvd. West, H3G1M8
Concordia University, Montreal, QC, Canada
E-Mail: haruty@cs.concordia.ca, cd_moros@cs.concordia.ca
Keywords: Knödel graphs, spectra of graphs, number of spanning trees Received: January 28, 2005
Knödel graphs Wdn are regular graphs on n vertices and degree d. They have been introduced by W. Knödel and have been proved to be minimum gossip graphs and minimum broadcast graphs for d = [log n\. They became even more interesting in the light of recent results regarding the diameter, which is, up to now, the smallest known diameter among all minimum broadcast graphs on 2d vertices. Also, the logarithmic time routing algorithm that we have found, the bipancyclicity property, embedding properties and, nevertheless, Cayley graph structure, impel these graphs as good candidates for regular network constructions, especially in supercomputing. In this paper we describe an efficient way to compute the spectra of Knödel graphs using results from Fourier analysis, circulant matrices and PD-matrices. Based on this result we give a formula for the number of spanning trees in Knödel graphs.
Povzetek: Narejenaje analiza Knödelovih grafov.
1 Introduction
Knödel graphs Wdn, are regular graphs on even number of vertices n and degree d. They have been introduced by W. Knödel [10] and have been proved to be minimum gossip graphs and minimum broadcast graphs for degree
d = [log2 n\.
Recently, it has been proved in [7] that the Knödel graph Wd 2d on 2d vertices and degree d have diameter \d/2 + 1], which is the minimum known diameter among all minimum broadcast graphs on 2d vertices. We believe that this is also a lower bound on diameter for all regular graphs on 2d vertices and degree d. Also, the logarithmic time routing algorithm that we have found [9], the bipan-cyclicity property, embedding properties and, nevertheless, Cayley graph structure [6], impel these graphs as good candidates for regular network constructions, especially in supercomputing.
The goal of this study is to compute efficiently the spectra of Knödel graphs, first for Wd 2d, and then for arbitrary degree g and number of vertices n. We use results from Fourier analysis, circulant matrices and PD-matrices. Based on this result we give a formula for the number of spanning trees in Knödel graphs.
The paper is organized as follows: section 2 gives some definitions, section 3 extracts the general properties of the spectra, section 4 explains the method of computation, section 5 makes some remarks regarding the obtained spectra and section 6 establishes the number of spanning trees.
2 Definitions and notations
If we denote by A the adjacency matrix of a simple graph G, the set of eigenvalues of A, together with their multiplicities, is said to be the spectrum of G. If we denote by I the identity matrix, then the characteristic polynomial of G is defined as P (A) = det |AI - A|. The spectrum of G will be the set of solutions of the equation P (A) = 0.
Knowing the spectrum of a graph has a great impact on other characteristics of the graph. For example, the com-
n— 1
plexity of a graph is k (G) = n Ü (An - Ak), where n
k=i
is the number of eigenvalues, and An is the greatest eigenvalue.
Up to now, the spectra are known for some particular graphs: path, cycle, complete graph, complete bipartite graph, complete tree, hypercube, fc-dimensional lattice, star graph, etc. (see [4] and [8] for further references).
The Knödel graphs Wgn are defined as G (V, E) with IVI = n even, and the set of edges [6]:
E = {(i,j) | i + j = 2k - 1 mod n } (1)
where k = 1, 2,..., g, 0 < i,j < n — 1, 1 < g < [log2 n\.
We denote the adjacency matrix of an undirected graph by A = [aj], where 1 < i,j < IV| = n, aj = 1 whenever vertex i is adjacent to vertex j, and 0 otherwise. If M is a matrix, we denote by MT the transpose of M, by M the complex conjugate of M, by M* the transpose complex conjugate of M, and by M—1 the inverse of M. We denote
296 Informatica 30 (2006) 295-299
H.A. Harutyunyan et al.
by n a permutation:
1
a (1)
2
a (2)
n a (n)
(2)
and by P (n) = (aij) the corresponding permutation ma-
trix of n, where a
i,a(i)
1 and aij=a(i)
0.
If z e C, we denote by Z the complex conjugate of z, and by ||z|| = %/ZZ the norm of z.
We denote by diag (Ai, A2,..., An) the diagonal matrix with the elements of the main diagonal (A1; A2,..., An).
Wedenote by circ (a1, a2,.., an) a circulant matrix with the first row (a1, a2,.., an). That is, the rest of the rows will be circular permutations of the first row toward right. Thus, it holds that aij = a1, i-j+1 mod n. If the step of the shift is an integer q = 1, we call this matrix a (q) circulant matrix [12].
We denote by r the inverse permutation matrix, which is a (-1)circulant: r = ( —1)circ (1,0,..., 0). An important property of r is that r2 = I, where I is the identity matrix.
We denote by F the Fourier matrix, defined by its conjugate transpose F* = -^n [w(i-1)(j-1)], 1 < i,j < n,
where w stands for the nth root of the unity [5]. Two important properties of F are: F* = F and FF * = I.
Other definitions and notations will follow in the places they are used.
3 General graph theory considerations
We observe that the adjacency matrix of the Knödel graphs is a (-l)circulant matrix, called also a retrocirculant [1], where all the rows are circular permutations of the first row toward left. For example, the adjacency matrix of W3 23 is:
01010001 10100010 01000101 1 0 0 0 1 0 1 0 00010101 00101010 01010100 0 1 0 1 0 0 0/
A
W3
(3)
W„
- All eigenvalues are real since the adjacency matrix is real and symmetric [3].
- The maximum eigenvalue is A= regular of degree g [2].
g, since Wg,n is
- All eigenvalues are symmetric with respect to zero [11] since the Knödel graph is bipartite and its characteristic polynomial has the form:
P (A) = An + a2An-2 + ... + a=-2A2 + a= (4)
- In particular, for Wd,2d, the number of distinct eigenvalues is at least |~d~| + 2 since the diameter is |~d~| +1 [4].
4 Computing the spectrum of Wd,2d
According to [5], a matrix A is (-1)circulant if and only if A = F* (rA) F, where A = diag (71,72,..., y=). This relation can be transformed in FAF* = rA. That means that A and rA have the same eigenvalue set [5]. The second term is a PD-matrix, defined as a product of two matrices, P and D, where P is a permutation matrix and D is a diagonal matrix. The characteristic polynomial of a PD-matrix can be computed by decomposing the permutation P in prime cycles of total length n [5]. Since Knödel graphs adjacency matrices are (-1)circulants, the problem resumes now to that of determining the values of j1,j2,..,jn. Since rA has the form:
rA
/71 0 ... 0 \
0 0 ... Yn
V 0 Y2 ... 0 )
(5)
[cij ] = rA and identify the ..., c„2 = 72. In order to perform the triple matrix multiplication FAF*, we note that:
we can perform FAF * = terms cn = Y1, c2= = Y=
—* 1 F = F =
n
n-(i-1)(j-1) mod 1
(6)
Since wn = 1 we may skip the modulo operations from the powers. Also, in order to avoid confusion with the summation indices, we emphasize the matrix indices. That is, [a]i j means that i is the row index and j is the column index, both varying from 1 to n.
FAF * =
Some general remarks can be made about the spectra of
1
n 1
n
1
n
,,-(i-1)(fc-1)
[ak, m]
k, m
k=1
,-(i-1)(k-1)
ak,
(m-1)(j-1)
(m-1)(j-1)
]Tw-(i-1)(k-1) a1,m+k-1
k=1 (m-1)(j-1)
w
(7)
Since in the first row of the adjacency matrix only d values are nonzero, we can change the variable of summation in
n
3
THE SPECTRA OF KNÖDEL GRAPHS
Informatica 30 (2006) 295-299 297
the first term of (7): k ^ r, where 1 < r < d. Therefore:
FAF * =
1
n
1
n
1
n
E
w
n id
-(i-1)(2r-m)
(m-1)(j-1)
E J2W-(i-1)(^w(m-1)(j-1)
m=1 \r=1
nd
w
1 r = 1
ww
-(i-1)(2r-m)w(m-1)(j-1)
i,j
Aitken proved in [1] that, for a (-l)circulant, Yn/2+1 = a1 — a2 + a3 —... — an, where (a1, a2,..., an) are the values of the first row of adjacency matrix. Thus:
Yn/2+1 = E(-1)i+1 = E(-1)2'+1 = -d (!5)
=1 j=1
For the rest of the eigenvalues we have to evaluate products of the form: Ytln-t+i, 2 < t < n/2. From (11) we have:
YtYn-t+2 =	g W2r(t-1)j ■
1
n
w-(j-1)J2 wm(j+i-2)J2 W-T(i-1)
m=1	r=1
Thus, for the general term of FAF * we obtain:
(8)
-(j-1) n	d
Ci . =	"ST wm(j+i-2)^ W-T -
n
ww
1	r=1
Yp Cn-p+2 ,
— w (p ^ > w> w
wmn
1	r=1
2r(n-(p-1))
But ^ wmn = n and w-2(n-(p-1)) = w2(p-1). Thus,
Yp = w-(p-1)J2 wT(p-1)
r=1
On the other hand, r matrix corresponds to the permutation:
* (r)
12 3 . 1 n n — 1 .
.. n/2+1 ... n .. n/2+1 ... 2
w-(n-t+^ V w2r(n-t+1)
(9)
r=1
w-(t-1)Yl w^(t-1M w(t-1)Y; w2r(n-t+1)\
r=1	r=1
d w2r(t-1) £ w2r- =
E
The general term of the TA matrix from (5) can be expressed as follows:
d w2r (t-1)d w2r (t-1) =
r=1	r=1
2
(10)
w
r=1
2r (t-1)
(16)
This confirms the well-known fact that all eigenvalues are real. Thus, the spectrum of Wd 2d is the set:
(11)
E'
2r (t-1)
(17)
This permutation can be decomposed	in
n/2+1 prime cycles of total length n [5,	1]:
(1) (2,n)... (n/2,n/2+ 2) (n/2+1). Thus, the characteristic polynomial will be:
P (A) = (A — yi) (X2 — Y2Yn) (X2 — Y3Yn-i) ...
... (A2 — Yn/2Yn/2+2) (A — Yn/2+1)	(12) The eigenvalues set will be:
S{Wd, 2*) = {±d}^± where 2 < t < n/2.
5 Observations
A. Not all eigenvalues are distinct. We can show that at most (n — 4)/2 of them are distinct. If we decompose the norm from (17) in its trigonometric form we obtain:
E<
r=1
2 (t-1)
2*
2*,
S = {Y1, ±a/y2Yn,	n-1: ...
-v ±^Yn/2Yn/2+2, Yn/2+1 } (13)
For the first eigenvalue we obtain:
d
Y1 = E 1 = d	(14)
r=1
(XJcosgd. 2r(t — 1)j+(XJ sin2d 2r(t — ])j (18)
We observe that this norm evaluates to the same value for
t = n/4 +1 — k, and t = n/4 + 1 + k:
2
(n/4+l-k-l)
r = 1
£ cos ^ 2r(? — k)) + (J>£ ^ ^
r=1
2* 2
r=1
n
2
298 Informatica 30 (2006) 295-299
H.A. Harutyunyan et al.
*{T+k)l	*■( ±-+k
E<
r=1
2d V 4
,2r (n/4+1+k-1)
2n „ J2
2d
j2w2r (2d/4)
r = 1 d
^cos^ + ^sm^
Vr = 1
Vr=1
x 2
-1 + 1 + 53«» ?2M + G+^sin V
r=3
r=2
(d - 2)2
Thus, for Wd 2d, the spectrum from (17) can be written as:
SWd2d
{±d, ±(d - 2)} U
uL
E<
,2r (i-1)
S
Wa
= {±3} UI ±
E'
,2r (i-1)
So2k = {±k}u{±
w2(i-1) + w4(i-1)
/ 2n 4 cos^k (t - 1)
Thus, we meet the well-known result [2] that the spectrum of a cycle of length n is the set:
(19)
Sc H 2 cos — j
Cn '	n
1 < j < n
(25)
The computations for particular cases yield to the claim that these are the only overlapping eigenvalues. B. To our knowledge, there is no closed form for the sum from (16). Nevertheless, computations for particular cases suggest that, only for the particular value t = 2d/4 +1, the sum is evaluated to a closed form:
6 The number of spanning trees
An immediate consequence of the spectra of the Knödel graphs Wgn is an O (ng2) formula for the number of spanning trees. It is well known that, given a graph G on n vertices and degree k, the number of spanning trees can be expressed as:
(g)=nn(k - ^r
p-1
(26)
i=1
where Xt are the eigenvalues, mt their multiplicities, and p the number of distinct eigenvalues [2]. Thus, for the particular case in which the degree is d and the number of vertices is 2d, using (21) we obtain:
(20)
K(Wdt2d) =
d(2d - 2)
2d-2
n (d2 -
i=2
E'
2r(i-1)
(27)
(21)
where 2 < t < n/4 and the last set has multiplicity two. C. Note that in the formulas (7)-(16) we didn't make any assumptions regarding the number of vertices n nor the degree d. Therefore, the result from (17) can be extended in a similar manner for Knödel graphs with arbitrary degree g and number of vertices n, Wgn:
If we further decompose the norm from (27) in its trigonometric form, we obtain:
E<
,2r (i-1)
^cosg 2r (t-1))+(£sin±d 2r (t-1)
2n,
vr=1
2d
Vr = 1
2d
(22)
dd
2n
d + E E cos^d (2* - 2?) (t - 1)
where 2 < t < n/2.
For example, for W2 2fc, which are cycles C2k of length 2k, applying (22), we obtain the spectrum:
*=1 j=*+1
(28)
(23)
Substituting this result in (27) and changing the variable t ^ t +1 we obtain for the number of spanning trees of
Wd,2d:
where 2 < t < 2k 1. The norm from (23) can be evaluated
to 2 cos 2n(t - 1)/2k as follows:
,2(i-1) + w4(i-1)
2n 2n cos 2k 2 (t - 1) + cos^k 4 (t - 1) J +
2n	,	2n , , ,
sin 2k 2 (t - 1) + sin 4 (t - 1) ) =
K(Wd,2*) =
2d-2 — 1
^^ n (d2 - d - *(t))2 (29)
i=1
where:
dd
2n
*(t)=E E cos-d (2* - 2?) t (30)
*=1j=*+1
2d
(24)
In general, for Knödel graphs having arbitrary degree g and arbitrary number of vertices n, Wgn, according to
d
d
2
2
K
2
2
2
2
d-2
2
2
2
THE SPECTRA OF KNÖDEL GRAPHS
Informatica 30 (2006) 295-299 297
(22), the number of spanning trees can be expressed as follows:
WW = ¥11U2 -
n/2
t=2
r=1
,2r (t-1)
(31)
A straightforward upper bound for the number of spanning trees of Knodel graphs Wgn can be obtained cancelling the norm from (31):
r=1
,2r (t 1)
(32)
Therefore, for k (Wgn) we obtain the upper bound:
k (Wg,n) <
2g
n— 1
(33)
[9] H. A. Harutyunyan and C. D. Morosan. On the minimum path problem in Knödel graphs. In Proceedings of the second international network optimization conference INOC2005, Lisbon, Portugal, pp. 43-48, 2005.
[10]	W. Knödel. New gossips and telephones. Discrete Mathematics, 13:95, 1975.
[11]	H. Sachs. Beziehungen zwischen den in einem graphen enthalten kreisen und seinem charakteristischen polynom. Publ. Math. Debrecen, 11:119-137, 1964.
[12]	K. Wang. On the generalisations of circulants. Linear algebra and its applications, 25:197-218, 1979.
Since, for Knödel graphs Wgn, the degree of a vertex g is upper bounded by |_log2 n\ (see (1)), the bound from (33) can be expressed as follows:
K (Wg,n) <
2 |log2 n\
1
(34)
2
K
2
0
n
n
References
[1]	A. C. Aitken. Two notes on matrices. In Proc. Glasgow Math. Ass., pages 109-113, Glasgow Math. Ass., 1961-1962.
[2]	N. L. Biggs. Algebraic Graph Theory. Cambridge University Press, 1974.
[3]	F. Chatelin and M. Ahu6s. Eigenvalues of Matrices. Chichester, Wiley, New York, 1993.
[4]	D. M. Cvetkovic, M. Doob, and H. Sachs. Spectra of Graphs. Academic Press, New York, 1980.
[5]	P. J. Davis. Circulant Matrices. Chichester, Wiley, New York, 1979.
[6]	G. Fertin and A. Raspaud. A survey on Knödel graphs. Discrete Applied Mathematics, 137(2):173-195, 2004.
[7]	G. Fertin, A. Raspaud, O. Sykora, H. Schröder, and I. Vrto. Diameter of Knödel graph. In 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000) in Lecture Notes in Computer Science, volume 1928, pages 149-160. Springer-Verlag, 2000.
[8]	C. Godsil and G. Royle. Algebraic Graph Theory. Springer-Verlag, New York, Berlin, Heidelberg, 2001.