On the connectivity and the conditional diameter of graphs and digraphs

✍ Scribed by Balbuena, C.; Carmona, A.; F�brega, J.; Fiol, M. A.

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 771 KB
• Volume: 28
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199609)28:2<97::aid-net3>3.0.co;2-7

✦ Synopsis

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D 5 21 -1, then G has maximum connectivity ( K = 6 ) . and if D 5 21, then it attains maximum edge-connectivity ( A = 6 ) , where I is a parameter which can be thought of as a generalization of the girth of a graph. In this paper, we study some similar conditions for a digraph to attain high connectivities, which are given in terms of what we call the conditional diameter or P-diameter of G. This parameter measures how far apart can be a pair of subdigraphs satisfying a given property P, and, hence, it generalizes the standard concept of diameter. As a corollary, some new sufficient conditions to attain maximum connectivity or edge-connectivity 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. In particular, since I 2 1, some known results of Plesnik and Znhm are either reobtained or improved. For instance, it is shown that any graph whose line graph has diameter D = 2 (respectively, D I 3) has maximum connectivity (respectively, edge-connectivity.) Moreover, for graphs with even girth and minimum degree large enough, we obtain a lower bound on their connectivities. CI 7996 John Wiley & Sons, Inc.