𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Diameter vulnerability of GC graphs

✍ Scribed by J. Gómez; I. Pelayo; C. Balbuena

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
469 KB
Volume
130
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Concern over fault tolerance in the design of interconnection networks has stimulated interest in ÿnding large graphs with maximum degree and diameter D such that the subgraphs obtained by deleting any set of s vertices have diameter at most D , this value being close to D or even equal to it. This is the so-called ( ; D; D ; s)-problem. The purpose of this work has been to study this problem for s=1 on some families of generalized compound graphs. These graphs were designed by GÃ omez (Ars Combin. 29-B (1990) 33) as a contribution to the ( ; D)-problem, that is, to the construction of graphs having maximum degree , diameter D and an order large enough. When approaching the mentioned problem in these graphs, we realized that each of them could be redeÿned as a compound graph, the main graph being the underlying graph of a certain iterated line digraph. In fact, this new characterization has been the key point to prove in a suitable way that the graphs belonging to these families are solutions to the ( ; D; D + 1; 1)-problem.

📜 SIMILAR VOLUMES

Vulnerability in graphs of diameter four
Vulnerability in graphs of diameter four
✍ Geoffrey Exoo; Frank Harary; Cheng-De Xu 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 285 KB

The analogue of Menger's Theorem on connectivity has been investigated for graphs of low diameter in which the removal of a set of lines increases the diameter. When the diameter is at most three, such a theorem has been proven already. Also, examples have been constructed to show that the result do

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 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.

Edge vulnerability parameters of bisplit
Edge vulnerability parameters of bisplit graphs
✍ Metrose Metsidik; Elkin Vumar 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 260 KB

A graph is called bisplit if its vertex set can be partitioned into three stable sets I, Y and Z such that Y ∪ Z induces a complete bipartite graph (a biclique). In this paper, we investigate the edge vulnerability parameters of bisplit graphs. Let G = (Y ∪ Z , I, E) be a noncomplete connected bispl