Bipartite graphs and digraphs with maximum connectivity
For a given bipartite digraph with diameter \(D\), let \(\ell\), \(1\leq \ell\leq D\), be the greatest integer such that for any two vertices \(x\) and \(y\) at distance \(d(x, y)\leq \ell\), the shortest \(x\)-\(y\) path is unique. The authors show that if the minimum degree \(\delta>1\) then the vertex connectivity \(\kappa=\delta\) whenever \(D\leq 2\ell\) and the edge connectivity \(\lambda=\delta\) whenever \(D\leq2\ell+1\). Analogous results are proved for bipartite graphs and for so-called superconnectivities.
scientific article; zbMATH DE number 933101
scientific article