Diameter-vulnerability of large bipartite digraphs

DOI10.1016/0166-218X(94)00127-YMaRDI QIDQ1917252zbMATH OpenWikidataFDO

Authors Carles Padró, Paz Morillo, E. Llobet

Publication date 21 November 1996

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(94)00127-Y

zbMATH Keywords

diametersdigraphpath

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• Diameter vulnerability of graphs
• On the diameter vulnerability of Kautz digraphs
• Diameter vulnerability of iterated line digraphs
• Diameter vulnerability of iterated line digraphs in terms of the girth
• Diameter vulnerability of graphs by edge deletion
• Vulnerability in graphs of diameter four
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• Line digraph iterations and diameter vulnerability
• New bounds on the diameter vulnerability of iterated line digraphs
• Diameters of random bipartite graphs

Cites work

• Dense bipartite digraphs
• scientific article; zbMATH DE number 3831957 (Why is no real title available?)
• scientific article; zbMATH DE number 3908346 (Why is no real title available?)
• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• scientific article; zbMATH DE number 4108811 (Why is no real title available?)
• scientific article; zbMATH DE number 4110714 (Why is no real title available?)
• Large (d,D, D',s)-bipartite digraphs
• Large fault-tolerant interconnection networks
• Line Digraph Iterations and the (d, k) Digraph Problem
• On the linegraph of a directed-graph
• The \((\Delta{} , d, d', \Delta{} - 1)\)-problem with applications to computer networks

Cited in

(8)

• Disjoint paths of bounded length in large generalized cycles
• Super link-connectivity of iterated line digraphs.
• Line digraph iterations and diameter vulnerability
• Large (d,D, D',s)-bipartite digraphs
• Diameter vulnerability of iterated line digraphs
• On large ( , D, D, 1)-graphs
• Diameter vulnerability of iterated line digraphs in terms of the girth
• New bounds on the diameter vulnerability of iterated line digraphs

This page was built for publication: Diameter-vulnerability of large bipartite digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917252)