This paper studies the relation between the connectivity and other parameters of a bipartite (di)graph G. Namely, its order n, minimum degree , maximum degree Δ, diameter D, and a new parameter related to the number of short paths in G. (When G is a bipartite — undirected — graph this parameter turns out to be , where g stands for its girth.) Let . As a main result, it is shown that if , then the connectivity of the bipartite digraph G is maximum. Similarly, if , then the arc-connectivity of G is also maximum. Some examples show that these results are best possible. Furthermore, we show that analogous results, formulated in terms of the girth, can be given for the undirected case.
展开▼
