Premium
Diameter vulnerability of iterated line digraphs in terms of the girth
Author(s) -
Balbuena C.,
Marcote X.,
Ferrero D.
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20049
Subject(s) - digraph , iterated function , combinatorics , mathematics , vulnerability (computing) , line (geometry) , girth (graph theory) , upper and lower bounds , iterated function system , discrete mathematics , computer science , fractal , mathematical analysis , geometry , computer security
Iterated line digraphs arise naturally in designing fault tolerant systems. Diameter vulnerability measures the increase in diameter of a digraph when some of its vertices or arcs fail. Thus, the study of diameter vulnerability is a suitable approach to the fault tolerance of a network. In this article we present some upper bounds for diameter vulnerability of iterated line digraphs L k G . Our bounds depend basically on the girth of the digraph G and on the number of iterations k . These bounds generalize some previous results on diameter vulnerability of line digraphs. Also, we apply our results to several important families of line digraphs such as Kautz digraphs and deBruijn generalized cycles, which contain deBruijn digraphs, the Reddy‐Pradhan‐Kuhl digraphs, and the butterflies. Our bounds allow us to obtain improvements in known results on diameter vulnerability for all these families. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 49‐54 2005