𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the diameter vulnerability of Kautz digraphs

✍ Scribed by D.Z. Du; D.F. Hsu; Y.D. Lyuu

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

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Diameter vulnerability of iterated line
Diameter vulnerability of iterated line digraphs
✍ C. PadrΓ³; P. Morillo πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 823 KB

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 a

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

On the superconnectivity and the conditi
On the superconnectivity and the conditional diameter of graphs and digraphs
✍ Carmona, A.; FοΏ½brega, J. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 142 KB πŸ‘ 2 views

It has been proved that if the diameter D of a digraph G satisfies D Υ… 2ᐉ Οͺ 2, where ᐉ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D Υ… 2ᐉ Οͺ 1, then G is edge-superconnected. In this paper, we studied some similar condi

On the connectivity and the conditional
On the connectivity and the conditional diameter of graphs and digraphs
✍ Balbuena, C.; Carmona, A.; FοΏ½brega, J.; Fiol, M. A. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 771 KB

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D 5 21 -1, then G has maximum connectivity ( K = 6 ) .