𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Superfluous edges and exponential expansions of De Bruijn and Kautz graphs

✍ Scribed by Eduardo A. Canale; José Gómez

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
644 KB
Volume
138
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

A new way to expand De Bruijn and Kautz graphs is presented. It consists of deleting super uous sets of edges (i.e., those whose removal does not increase the diameter) and adding new vertices and new edges preserving the maximum degree and the diameter. The number of vertices added to the Kautz graph, for a ÿxed maximum degree greater than four, is exponential on the diameter. Tables with lower bounds for the order of super uous sets of edges and the number of vertices that can be added, are presented.

📜 SIMILAR VOLUMES

Bisecting de Bruijn and Kautz graphs
Bisecting de Bruijn and Kautz graphs
✍ José Rolim; Pavel Tvrdik; Jan Trdlička; Imrich Vrto 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 675 KB

De Bruijn and Kautz graphs have been intensively studied as perspective interconnection networks of massively parallel computers. One of the crucial parameters of an interconnection network is its bisection width. It has an influence on both communication properties of the network and the algorithmi

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

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