On the superconnectivity and the conditional diameter of graphs and digraphs

✍ Scribed by Carmona, A.; F�brega, J.

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 142 KB
• Volume: 34
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199910)34:3<197::aid-net4>3.0.co;2-9

✦ Synopsis

It has been proved that if the diameter D of a digraph G satisfies D Յ 2ᐉ Ϫ 2, where ᐉ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D Յ 2ᐉ Ϫ 1, then G is edge-superconnected. In this paper, we studied some similar conditions for a digraph to attain superconnectivity, which are given in terms of the conditional diameter or ᏼ-diameter of G. This parameter measures how far apart can be a pair of subdigraphs satisfying a given property ᏼ, and, hence, it generalizes the standard concept of the diameter. As a corollary, some new sufficient conditions to attain superconnectivity or edge-superconnectivity are derived. It is also shown that these conditions can be slightly relaxed when the digraphs are bipartite. The case of (undirected) graphs is managed as a corollary of the above results for digraphs.