✦ LIBER ✦

The Spectrum of de Bruijn and Kautz Graphs

✍ Scribed by C. Delorme; J.-P. Tillich

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 187 KB
Volume: 19
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1997.0183

No coin nor oath required. For personal study only.

✦ Synopsis

We give here a complete description of the spectrum of de Bruijn and Kautz graphs. It is well known that spectral techniques have proved to be very useful tools to study graphs, and we give some examples of application of our result, by deriving tight bounds on the expansion parameters of those graphs.

📜 SIMILAR VOLUMES

De Bruijn and Kautz bus networks

✍ Bermond, Jean-Claude; Dawes, Robin W.; Ergincan, Fahir �. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 598 KB

Our aim was to find bus interconnection networks which connect as many processors as possible, for given upper bounds on the number of connections per processor, the number of processors per bus, and the network diameter. Point-to-point networks are a special case of bus networks in which every bus

On even factorizations and the chromatic

On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs

✍ Jean-Claude Bermond Cnrs; Pavol Hell 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB

## Abstract Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in‐ and outdegree __d__ have arc‐chromatic index __2d__. In order to do this, we introduce the concept of even 1‐factorizations. An even 1‐factor of a digraph is a spann

2-diameter of de Bruijn graphs

✍ Li, Qiao; Sotteau, Dominique; Xu, Junming 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 589 KB

This paper shows that in the undirected binary de Bruijn graph of dimension n . UB(n), which has diameter n , there exist at least two internally vertex disjoint paths of length at most n between any two vertices. In other words, the 2-diameter of U B ( n ) is equal to its diameter n .

Embedding Cartesian Products of Graphs i

Embedding Cartesian Products of Graphs into de Bruijn Graphs

✍ Thomas Andreae; Michael Nölle; Gerald Schreiber 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 172 KB

## Given a Cartesian product G of nontrivial connected graphs G i and the n-dimensional base B de Bruijn graph D = D B (n), it is investigated whether or not G is a spanning subgraph of D. Special attention is given to graphs G 1 × • • • × G m which are relevant for parallel computing, namely, to

On the diameter of the generalized undir

On the diameter of the generalized undirected de Bruijn graphs UGB(n,m), n2 m ≤ n3

✍ Jyhmin Kuo; Hung-Lin Fu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB

## Abstract The generalized de Bruijn digraph __G__~__B__~(__n__,__m__) is the digraph (__V__,__A__) where __V__ = {0, 1,…,__m__ − 1} and (__i__,__j__) ∈ __A__ if and only if __j__ ≡ __i____n__+__α__ (mod __m__) for some __α__ ∈ {0, 1, 2,…,__n__− 1}. By replacing each arc of __G__~__B__~(__n__,__m_

On the Spectrum, the Growth, and the Dia

On the Spectrum, the Growth, and the Diameter of a Graph

✍ N. Hajaj 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 171 KB

A lower bound is given for the harmonic mean of the growth in a finite undirected graph 1 in terms of the eigenvalues of the Laplacian of 1. For a connected graph, this bound is tight if and only if the graph is distance-regular. Bounds on the diameter of a ``sphere-regular'' graph follow. Finally,