𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Diameter vulnerability of iterated line digraphs

✍ Scribed by C. Padró; P. Morillo

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
823 KB
Volume
149
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For any digraph G, we find a constant C (not greater than twice the diameter of G) such that, under certain conditions, the diameter vulnerability of the iterated line digraph LkG is at most the diameter of LkG plus C. The results in this paper generalize previous results on the diameter-vulnerability of particular families of iterated line digraphs (Kautz and de Bruijn digraphs).

📜 SIMILAR VOLUMES

On the diameter vulnerability of Kautz d
On the diameter vulnerability of Kautz digraphs
✍ D.Z. Du; D.F. Hsu; Y.D. Lyuu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 223 KB

We show that in the Kautz digraph K(d, t) with d' + d'-1 vertices each having out degree d, there exist d vertex-disjoint paths between any pair of distinct vertices, one of length at most t, d -2 of length at most t + 1, and one of length at most t + 2.

Maximum diameter of regular digraphs
Maximum diameter of regular digraphs
✍ Josè Soares 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 512 KB

## Abstract We prove that every __r__‐biregular digraph with __n__ vertices has its directed diamter bounded by (3__n__ ‐ __r__ ‐ 3)/(__r__ +1). We show that this bound is tight for directed as well as for undirected graphs. The upper bound remains valid for Eulerian digraphs with minimum outdegree

Convergent sequences of iterated H-line
Convergent sequences of iterated H-line graphs
✍ Gary Chartrand; Heather Gavlas; Michelle Schultz 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 629 KB

For a connected graph H of order at least 3, the H-line graph HL(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of HL(G) are adjacent if and only if the corresponding edges of G are adjacent and belong to a common copy of H. For k >~ 2, the kth ite