Affordable Access

Publisher Website

Diameter vulnerability of iterated line digraphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
149
Identifiers
DOI: 10.1016/0012-365x(96)83094-9
Disciplines
  • Design

Abstract

Abstract 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 L k G is at most the diameter of L k G 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).

There are no comments yet on this publication. Be the first to share your thoughts.