✦ LIBER ✦

2-diameter of de Bruijn graphs

✍ Scribed by Li, Qiao; Sotteau, Dominique; Xu, Junming

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 589 KB
Volume: 28
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199608)28:1<7::aid-net2>3.0.co;2-j

No coin nor oath required. For personal study only.

✦ Synopsis

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 .

📜 SIMILAR VOLUMES

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_

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

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

Maximum degree in graphs of diameter 2

✍ Paul Erdös; Siemion Fajtlowicz; Alan J. Hoffman 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

Minimum vertex-diameter-2-critical graph

Minimum vertex-diameter-2-critical graphs

✍ Ya-Chen Chen; Zoltán Füredi 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

## Abstract We prove that the minimum number of edges in a vertex‐diameter‐2‐critical graph on __n__ ≥ 23 vertices is (5__n__ − 17)/2 if __n__ is odd, and is (5__n__/2) − 7 if __n__ is even. © 2005 Wiley Periodicals, Inc. J Graph Theory

Almost all steinhaus graphs have diamete

Almost all steinhaus graphs have diameter 2

✍ Neal Brand 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 1 views

## Abstract A Steinhaus graph is a graph with __n__ vertices whose adjacency matrix (__a__~i, j~) satisfies the condition that __a__~i, j~  __a__~a‐‐1, j‐‐1~ + __a__ ~i‐‐1, j~ (mod 2) for each 1 < __i__ < __j__ ≤ __n__. It is clear that a Steinhaus graph is determined by its first row. In [3] Brin