✦ LIBER ✦

Independence number of de Bruijn graphs

✍ Scribed by Nicolas Lichiardopol

Book ID: 108113586
Publisher: Elsevier Science
Year: 2006
Tongue: English
Weight: 264 KB
Volume: 306
Category: Article
ISSN: 0012-365X
DOI: 10.1016/j.disc.2005.10.032

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Generalized de Bruijn graphs

✍ F. M. Malyshev; V. E. Tarakanov 📂 Article 📅 1997 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 606 KB

Wide diameters of de Bruijn graphs

✍ Jyhmin Kuo; Hung-Lin Fu 📂 Article 📅 2007 🏛 Springer US 🌐 English ⚖ 288 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 .

Extension of de Bruijn graph and Kautz g

Extension of de Bruijn graph and Kautz graph

✍ Y. Shibata; Y. Gonda 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 560 KB

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

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