✦ LIBER ✦

Spanners of de Bruijn and Kautz graphs

✍ Scribed by Rabah Harbane; Carles Padró

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 530 KB
Volume: 62
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00075-6

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Spectrum of de Bruijn and Kautz Grap

The Spectrum of de Bruijn and Kautz Graphs

✍ C. Delorme; J.-P. Tillich 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 187 KB

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 grap

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

Fault-tolerant routings in Kautz and de

Fault-tolerant routings in Kautz and de Bruijn networks

✍ Nathalie Homobono; Claudine Peyrat 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 321 KB

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 .

A note on recursive properties of the de

A note on recursive properties of the de Bruijn, Kautz and FFT digraphs

✍ M.C Heydemann; D Sotteau 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 437 KB

On the domination numbers of generalized

On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs

✍ Yosuke Kikuchi; Yukio Shibata 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 94 KB

This work deals with the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs. Dominating sets for digraphs are not familiar compared with dominating sets for undirected graphs. Whereas dominating sets for digraphs have more applications than those for undirected graph