Recently, some sufficient conditions for a digraph to have maximum connectivity or high superconnectivity have been given in terms of a new parameter which can be thought of as a generalization of the girth of a graph. In this paper similar results are derived for bipartite digraphs and graphs showing that, in this case, all the known conditions can be improved. As a corollary, it is shown that any bipartite graph of girth g and diameter D g - 2 (respectively D g - 1) has maximum vertex-connectivity (respectively maximum edge-connectivity). This implies a result of Plesnik and Znám stating that any bipartite graph with diameter three is maximally edge-connected.
展开▼
