Diameter-vulnerability of large bipartite digraphs
type: Item
instance of: scholarly article
title: Diameter-vulnerability of large bipartite digraphs
zbMATH Open document ID: 0851.05055
DOI: 10.1016/0166-218X(94)00127-Y
author: Carles Padró
author: Paz Morillo
author: E. Llobet
published in: Discrete Applied Mathematics
publication date: 1996-11-21T00:00:00Z
review text: The \(s\)-diameter-vulnerability of a digraph \(G\) is the maximum of the diameters of the digraphs formed by removing \(s\) arbitrary vertices from \(G\). Among all bipartite digraphs with \(n\) vertices and maximum out-degree \(d\), the paper gives a lower bound for the \(s\)-diameter-vulnerability; and for \(n= 2(d^{D- 1}+ d^{D-3})\) there are bipartite digraphs with \(s\)-diameter-vulnerability at most one larger than this lower bound, where \(D\) is the diameter. An algorithm is given for finding a path of length at most \(D+ 2\) between any pair of vertices even if some vertices are faulty.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 897365
zbMATH Keywords: digraph
zbMATH Keywords: diameters
zbMATH Keywords: path
Wikidata QID: Q63958690
MaRDI profile type: Publication
cites work: On the linegraph of a directed-graph
cites work: Q3039368
cites work: Large fault-tolerant interconnection networks
cites work: Q3686639
cites work: Q3834069
cites work: Q3818315
cites work: Dense bipartite digraphs
cites work: Line Digraph Iterations and the (d, k) Digraph Problem
cites work: Large \((d,D, D',s)\)-bipartite digraphs
cites work: Q3832603
cites work: The \((\Delta{} , d, d', \Delta{} - 1)\)-problem with applications to computer networks
Recommended article: Diameter vulnerability of graphs
Recommended article: On the diameter vulnerability of Kautz digraphs
Recommended article: Diameter vulnerability of iterated line digraphs
Recommended article: Diameter vulnerability of iterated line digraphs in terms of the girth
Recommended article: Diameter vulnerability of graphs by edge deletion
Recommended article: Vulnerability in graphs of diameter four
Recommended article: On a problem of a. kotzig concerning factorizations of 4‐regular graphs
Recommended article: Line digraph iterations and diameter vulnerability
Recommended article: New bounds on the diameter vulnerability of iterated line digraphs
Recommended article: Diameters of random bipartite graphs
description: scientific article; zbMATH DE number 897365