21,435,892 articles and books

# 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 logarithmic

pertaining to logarithm.

logarithmic relationship
when the logs of two variables plotted against each other create a straight line.
time routing algorithm that we have found, the bipancyclicity property, embedding properties and, nevertheless, Cayley graph In mathematics, a Cayley graph (also known as a Cayley colour graph and named after Arthur Cayley), is a graph that encodes the structure of a group. It is a central tool in combinatorial and geometric group theory.

Given a group
structure, impel im·pel
tr.v. im·pelled, im·pel·ling, im·pels
1. To urge to action through moral pressure; drive: I was impelled by events to take a stand.

2. To drive forward; propel.
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 Fourier analysis
n.
The branch of mathematics concerned with the approximation of periodic functions by the Fourier series and with generalizations of such approximations to a wider class of functions.
, 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 In mathematics and computer science, the adjacency matrix of a finite directed or undirected graph G on n vertices is the n × n matrix where the nondiagonal entry  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 This article is about the characteristic polynomial of a matrix. For the characteristic polynomial of a matroid or graded poset, see Graded poset.

In linear algebra, one associates a polynomial to every square matrix, its 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 ASCII or American Standard Code for Information Interchange, a set of codes used to represent letters, numbers, a few symbols, and control characters. Originally designed for teletype operations, it has found wide application in computers. .], where n is the number of eigenvalues, and [[lambda].sub.n] is the greatest eigenvalue eigenvalue

In mathematical analysis, one of a set of discrete values of a parameter, k, in an equation of the form Lx = kx. Such characteristic equations are particularly useful in solving differential equations, integral equations, and systems of
.

Up to now, the spectra are known for some particular graphs: path, cycle, complete graph complete graph - A graph which has a link between every pair of nodes. A complete bipartite graph can be partitioned into two subsets of nodes such that each node is joined to every node in the other subset. , complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. , complete tree, hypercube A parallel processing architecture made up of binary multiples of computers (4, 8, 16, etc.). The computers are interconnected so that data travel is kept to a minimum. For example, in two eight-node cubes, each node in one cube would be connected to the counterpart node in the other. , 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 trans·pose
v.
To transfer one tissue, organ, or part to the place of another.
of M, by [bar.M] the complex conjugate complex conjugate
n.
Either one of a pair of complex numbers whose real parts are identical and whose imaginary parts differ only in sign; for example, 6 + 4i and 6 - 4i are complex conjugates.

Noun 1.
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 One possible combination of items out of a larger set of items. For example, with the set of numbers 1, 2 and 3, there are six possible permutations: 12, 21, 13, 31, 23 and 32.

(mathematics) permutation - 1.
:

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

and by P ([pi]) = ([a.sub.ij]) the corresponding permutation matrix In mathematics, in matrix theory, a permutation matrix is a square (0,1)-matrix that has exactly one entry 1 in each row and each column and 0's elsewhere. Each such matrix represents a specific permutation of m elements and, when used to multiply another matrix, can produce that  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 Noun 1. diagonal matrix - a square matrix with all elements not on the main diagonal equal to zero
square matrix - a matrix with the same number of rows and columns

scalar matrix - a diagonal matrix in which all of the diagonal elements are equal
with the elements of the main diagonal Noun 1. main diagonal - the diagonal of a square matrix running from the upper left entry to the lower right entry
principal diagonal

diagonal - an oblique line of squares of the same color on a checkerboard; "the bishop moves on the diagonals"
([[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)

--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 FAF
abbr.
financial aid form
.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 A mathematical operation (modulus arithmetic) in which the result is the remainder of a division. Also known as the "remainder operator," it is used to solve a variety of problems. For example, the following code in the C language determines if a number is odd or even.  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 non·ze·ro
Not equal to zero.

nonzero

Not equal to zero.
, 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 de·com·pose
v. de·com·posed, de·com·pos·ing, de·com·pos·es

v.tr.
1. To separate into components or basic elements.

2. To cause to rot.

v.intr.
1.
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 Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs.

In one sense, algebraic graph theory studies graphs in connection with linear algebra.
. Cambridge University Press Cambridge University Press (known colloquially as CUP) is a publisher given a Royal Charter by Henry VIII in 1534, and one of the two privileged presses (the other being Oxford University Press). , 1974.

[3] F. Chatelin and M. Ahues. Eigenvalues of Matrices. Chichester, Wiley, New York New York, state, United States
New York, Middle Atlantic state of the United States. It is bordered by Vermont, Massachusetts, Connecticut, and the Atlantic Ocean (E), New Jersey and Pennsylvania (S), Lakes Erie and Ontario and the Canadian province of
, 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 Lecture Notes in Computer Science (LNCS) is a computer science series published by Springer Science+Business Media. , 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 INOC INOC Internet Network Operations Center
INOC Iranian National Oil Company
INOC Inoculate/Inoculation
INOC International Network Operation Center
INOC Iran National Oil Company
INOC Income Net of Claims
2005, 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

E-Mail: haruty@cs.concordia.ca, cd_moros@cs.concordia.ca

No portion of this article can be reproduced without the express written permission from the copyright holder.

Title:

Comment:

Author: Printer friendly Cite/link Email Feedback Harutyunyan, Hovhannes A.; Morosan, Calin D. Informatica 1CANA Oct 1, 2006 3093 Expected case for projecting points. On the crossing number of almost planar graphs. Fourier analysis Graphic methods Grid computing