The spectra of Knodel graphs.

Knodel graphs [W.sub.d,n] are regular graphs on n vertices and degree d. They have been introduced by W. Knodel 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 [2.sup.d] 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 Knodel 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 Knodel graphs.

Povzetek: Narejena je analiza Knodelovih grafov.

Keywords: Knodel graphs, spectra of graphs, number of spanning trees

1 Introduction

Knodel graphs [W.sub.d,n], are regular graphs on even number of vertices n and degree d. They have been introduced by W. Knodel [10] and have been proved to be minimum gossip graphs and minimum broadcast graphs for degree d = [[log.sub.2] n].

Recently, it has been proved in [7] that the Knodel graph [W.sub.d,2d] on [2.sup.d] vertices and degree d have diameter [d/2 + 1], which is the minimum known diameter among all minimum broadcast graphs on [2.sup.d] vertices. We believe that this is also a lower bound on diameter for all regular graphs on [2.sup.d] vertices and degree d. Also, the logarithmic time routing algorithm that we have found [9], the bipancyclicity 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 Knodel graphs, first for [W.sub.d,[2.sup.d]], 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 Knodel 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 ([lambda]) = det [[lambda]I - A]. The spectrum of G will be the set of solutions of the equation P ([lambda]) = 0.

Knowing the spectrum of a graph has a great impact on other characteristics of the graph. For example, the complexity of a graph is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], where n is the number of eigenvalues, and [[lambda].sub.n] 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, k-dimensional lattice, star graph, etc. (see [41 and [8] for further references).

The Knodel graphs [W.sub.g,n] are defined as G (V, E) with |V| = n even, and the set of edges [6]:

E = {(i,j) |i + j = [2.sup.k] - l mod n} (1)

where k = 1,2 ..., g, 0 [less than or equal to] i,j [less than or equal to] n-1, 1 [less than or equal to] g [less than or equal to] [[log.sub.2] n].

We denote the adjacency matrix of an undirected graph by A = [[a.sub.ij]], where 1 [less than or equal to] i,j [less than or equal to] |V| = n, [a.sub.ij] = 1 whenever vertex i is adjacent to vertex j, and 0 otherwise. If M is a matrix, we denote by [M.sup.T] the transpose of M, by [bar.M] the complex conjugate of M, by [M.sup.*] the transpose complex conjugate of M, and by [M.sup.-1] the inverse of M. We denote by [pi] a permutation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], (2)

and by P ([pi]) = ([a.sub.ij]) the corresponding permutation matrix of [pi], where [a.sub.i,[sigma],(i)] = 1 and [a.sub.i,j[not equal to][sigma](i)] = 0.

If z [member of] [??], we denote by [bar.z] the complex conjugate of z, and by [parallel]z[parallel]= [square root of z[bar.z]] the norm of z.

We denote by diag ([[lambda].sub.1], [[lambda].sub.2],..., [[lambda].sub.n]) the diagonal matrix with the elements of the main diagonal ([[lambda].sub.1], [[lambda].sub.2],..., [[lambda].sub.n]).

We denote by circ ([a.sub.1], [a.sub.2],..., [a.sub.n]) a circulant matrix with the first row ([a.sub.1], [a.sub.2],..., [a.sub.n]). That is, the rest of the rows will be circular permutations of the first row toward right. Thus, it holds that [a.sub.i,j] = [a.sub.1] i-j+1 mod n. If the step of the shift is an integer q [not equal to] 1, we call this matrix a (q)circulant matrix [12].

We denote by [GAMMA] the inverse permutation matrix, which is a (-1) circulant: [GAMMA] = (-1) circ (1, 0,..., 0). An important property of [GAMMA] is that [[GAMMA].sup.2] = I, where I is the identity matrix.

We denote by F the Fourier matrix, defined by its conjugate transpose [F.sup.*] = 1/[square root of n]] [[w.sup.(i-1)](j-1)]1, [less than or equal to] i,j [less than or equal to] n, where w stands for the [n.sup.th] root of the unity [5]. Two important properties of F are: [F.sup.*] = [bar.F] and [FF.sup.*] = 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 Knodel graphs is a (-1) 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 [W.sub.3,[2].sup.3] is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

Some general remarks can be made about the spectra of [W.sub.g,n]:

--All eigenvalues are real since the adjacency matrix is real and symmetric [3].

--The maximum eigenvalue is [[lambda].sub.n] = g, since [W.sub.g,n] is regular of degree 9 [2].

--All eigenvalues are symmetric with respect to zero [11] since the Knodel graph is bipartite and its characteristic polynomial has the form:

P ([lambda]) = [[lambda].sup.n] + [[a.sub.2][lambda].sup.n-2] + ... + [a.sub.n-2] [[lambda].sup.2] + [a.sub.n] (4)

--In particular, for [W.sub.d,[2.sup.d]], the number of distinct eigenvalues is at least [d/2] + 2 since the diameter is [d/2] + 1 [4].

4 Computing the spectrum of [W.sub.d,2d]

According to [5], a matrix A is (-1)circulant if and only if A = [F.sup.*] ([GAMMA]A) F, where A = diag ([[gamma].sub.1] [[gamma].sub.2] ..., [[gamma].sub.n]). This relation can be transformed in [FAF.sup.*] = [GAMMA]A. That means that A and [GAMMA]A 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 Knodel graphs adjacency matrices are (-1)circulants, the problem resumes now to that of determining the values of [[gamma].sub.1], [[gamma].sub.2],..., [[gamma].sub.n]. Since [GAMMA]A has the form:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (5)

we can perform [FAF.sup.*] = [[c.sub.ij]] = FA and identify the terms [C.sub.11] = [[gamma].sub.1], [C.sub.2n]: [[gamma].sub.n],..., [C.sub.n2] [[gamma].sub.2]. In order to perform the triple matrix multiplication [FAF.sup.*], we note that:

F = [[bar.F].sup.*]= 1/[square root n] [w-(i-1)(j-1)mod n] (6)

Since [w.sup.n] = 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].sub.i,j] means that i is the row index and j is the column index, both varying from 1 to n.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (7)

Since in the first row of the adjacency matrix only d values are nonzero, we can change the variable of summation in the first term of (7): k [right arrow] r, where 1 [less than or equal to] r [less than or equal to] d. Therefore:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (8)

Thus, for the general term of [FAF.sup.*] we obtain:

[c.sub.i,j] = [w.sup.-(j-1)]/n [n.summation over (m=1)] [w.sup.m(j+1-2)] [d.summation over (r=1)] [w.sup.-[2.sup.r](i-1)] (9)

The general term of the [GAMMA][LAMBDA] matrix from (5) can be expressed as follows:

[[gamma].sub.p] = [c.sub.n-p]+2,p =

1/n [w.sup.-(p-1)] [n.summation over (m=1)] [w.sup.mn] [d.summation over (r=1)] [w.sup.-[2.sup.r](n-(p-1))] (10)

But [n.summation over (m=1)] [w.sup.mn] = n and [w.sup.-[2.sup.r](n-(p-1))] = [w.sup.[2.sup.r](p-1)]. Thus,

[[gamma].sub.p] = [w.sup.-(p-1)] [d.summation over (r=1)] [w.sup.[2.sup.r](p-1)] (11)

On the other hand, [GAMMA] matrix corresponds to the permutation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

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 ([lambda]) = ([lambda] - [[gamma].sub.1]) ([[lambda].sup.2] - [[gamma].sub.2] [[gamma].sub.n]) ([[lambda].sup.2] - [[gamma].sub.3] [[gamma].sub.n-1]) ... ... ([[lambda].sup.2] - [[gamma].sub.n]/2[[gamma].sub.n]/2+2) ([lambda] - [[gamma].sub.n]/2+1) (12)

The eigenvalues set will be:

S = {[[gamma].sub.1], [+ or -] [square root of [[gamma].sub.2] [[gamma].sub.n]], [+ or -] [square root of [[gamma].sub.3] [[gamma].sub.n-1]],... ..., [+ or -] [square root of [[gamma].sub.n]2[[gamma].sub.n]]/2+2], [[gamma].sub.n]/2+1} (13)

For the first eigenvalue we obtain:

[[gamma].sub.1] [d.summation over (r=1)] 1 = d (14)

Aitken proved in [1] that, for a (-1) circulant, [[gamma].sub.n]/2+1 = [a.sub.1] - [a.sub.2] + [a.sub.3] - ... - [a.sub.n], where ([a.sub.1], [a.sub.2],..., [a.sub.n]) are the values of the first row of adjacency matrix. Thus:

[[gamma].sub.1]/2+1 = [n.summation over (i=1)] [(-1).sup.i+1][a.sub.i] = [d.summation over (j=1)] [(-1).sup.2j+1] = -d (15)

For the rest of the eigenvalues we have to evaluate products of the form: [[gamma].sub.t][[gamma].sub.n-t+2], 2 [less than or equal to] t [less than or equal to] n/2. From (11) we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (16)

This confirms the well-known fact that all eigenvalues are real. Thus, the spectrum of [W.sub.d,[2.sup.d]] is the set:

S ([W.sub.d,[2.sup.d]]) = {[+ or -]d} [union] { [+ or -] [parallel] [d.summation over (r=1)] [w.sup.[2.sup.r]](t-1) [parallel]} (17)

where 2 [less than or equal to] t [less than or equal to] 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:

[[parallel][d.summation over (r=1)] [w.sup.[2.sup.r](t-1)] [parallel].sup.2] = [([d.summation over (r=1)] cos 2[pi]/[2.sup.d][2.sup.r] (t-1)).sup.2] + [([d.summation over (r=1)] sin 2[pi]/[2.sup.d] [2.sup.r](t-1)).sup.2] (18)

We observe that this norm evaluates to the same value for t = n/4 + 1 - k, and t = n/4 + 1 + k:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (19)

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 = [2.sup.d]/4 + 1, the sum is evaluated to a closed form:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (20)

Thus, for [W.sub.d,[2.sup.d]], the spectrum from (17) can be written as:

[S.sub.[W.sub.d,[2.sup.d]]] = {[+ or -]d, [+ or -] (d - 2)} [union] [union]{[+ or -] [parallel] [d.summation over (r=1)] [w.sup.[2.sup.r](t- 1)][parallel]} (21)

where 2 [less than or equal to] t [less than or equal to] 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 Knodel graphs with arbitrary degree g and number of vertices n, [W.sub.g,n]:

[S.sub.[W.sub.g,n]] = {[+ or -]g} [union] {[+ or -] [parallel] [g.summation over (r=1)] [w.sup.[2.sup.r](t-1)][parallel]} (22)

where 2 [less than or equal to] t [less than or equal to] n/2.

For example, for [W.sub.2,[2.sup.k]], which are cycles [C.sub.[2.sup.k]] of length [2.sup.k], applying (22), we obtain the spectrum:

[S.sub.[C.sub.[2.sup.k]]] = {[+ or -]k} [union] {[+ or -] [parallel] [w.sup.2 (t-1)] + [w.sup.4(t-1)] [parallel]} (23)

where 2 [less than or equal to] t [less than or equal to] [2.sup.k-1]. The norm from (23) can he evaluated to 2 cos 2[pi](t - 1)/[2.sup.k] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (24)

Thus, we meet the well-known result [2] that the spectrum of a cycle of length n is the set:

[S.sub.[c.sub.n]] = {2 cos 2[pi]j/n | 1 [less than or equal to] j [less than or equal to] n} (25)

6 The number of spanning trees

An immediate consequence of the spectra of the Knodel graphs [W.sub.g,n] is an O ([ng.sup.2]) 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:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (26)

where [[lambda].sub.t] are the eigenvalues, [m.sub.t] 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 [2.sup.d], using (21) we obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (27)

If we further decompose the norm from (27) in its trigonometric form, we obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (28)

Substituting this result in (27) and changing the variable t [right arrow] t + 1 we obtain for the number of spanning trees of [W.sub.d,[2.sup.d]]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (29)

where:

[PHI](t) = [d.summation over (i=1)] [d.summation over (j-i+1)] cos 2[pi]/[2.sup.d]([2.sup.i] - [2.sup.j])t (30)

In general, for Knodel graphs having arbitrary degree g and arbitrary number of vertices n, [W.sub.g,n], according to (22), the number of spanning trees can be expressed as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (31)

A straightforward upper bound for the number of spanning trees of Knodel graphs [W.sub.g,n] can be obtained cancelling the norm from (31):

[[parallel][g.summation over (r=1)][w.sup.[2.sup.r]](t-1)[parallel].sup.2] = 0

Therefore, for [kappa] ([W.sub.g,n]) we obtain the upper bound:

[kappa] ([W.sub.g,n]) [less than or equal to] 2[g.sup.n-1]/n (33)

Since, for Knodel graphs ([W.sub.g,n]) the degree of a vertex g is upper bounded by [[log.sub.2] n] (see (1)), the bound from (33) can be expressed as follows:

[kappa] ([W.sub.g,n]) [less than or equal to] 2[[log.sub.2] n].sup.n-1]/n (34)

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. Ahues. Eigenvalues of Matrices. Chichester, Wiley, New York, 1993.

[41 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 Knodel graphs. Discrete Applied Mathematics, 137(2): 173-195, 2004.

[7] G. Fertin, A. Raspaud, O. Sykora, H. Schroder, and I. Vrto. Diameter of Knodel 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.

[9] H. A. Harutyunyan and C. D. Morosan. On the minimum path problem in Knodel graphs. In Proceedings of the second international network optimization conference INOC2005, Lisbon, Portugal, pp. 43-48, 2005.

[10] W. Knodel. 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.

Hovhannes A. Harutyunyan and Calin D. Morosan

Department of Computer Science

1455 de Maisonneuve Blvd. West, H3G1M8

Concordia University, Montreal, QC, Canada

E-Mail: [e-mail], [e-mail]

Received: January 28, 2005