Connectedness of digraphs and graphs under constraints on the conditional diameter
Given a digraph G with minimum degree 8 and an integer 0 less than or equal to nu less than or equal to delta, consider every pair of vertex subsets V-1 and V-2 such that both the minimum out-degree of the induced subdigraph G[V-1] and the minimum in-degree of G[V-2] are at least v. The conditional diameter D, of G is defined as the maximum of the distances d(V-1, V-2) between any two such vertex subsets. Clearly, D-0 is the standard diameter and D-0 greater than or equal to D-1 greater than or equal to (...) D-delta holds. In this article, we guarantee appropriate lower bounds for the connectivities and superconnectivities of a digraph G when D-v less than or equal to h(l(pi)), h(l(pi)) being a function of the parameter l(pi)-which is related to the shortest paths in G. As a corollary of these results, we give some constraints of the kind D-nu less than or equal to h(l(pi)), which assure that the digraph is maximally connected, maximally edge-connected, superconnected, or edge-superconnected, extending other previous results of the same kind. Similar statements can be obtained for a graph as a direct consequence of those for its associated symmetric digraph. (C) 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2),80-87 2005
connectivity digraphs diameter superconnectivity fault-tolerance