Local-edge-connectivity in digraphs and oriented graphs

A digraph without any cycle of length two is called an oriented graph. The local-edge-connectivity lambda(u, v) of two vertices it and v in a digraph or graph D is the maximum number of edge-disjoint u-v paths in D, and the edge-connectivi y of D is defined as lambda(D) = min{lambda(u,v)vertical bar u, v is an element of V(D);u not equal v}. Clearly, lambda(u, v) <= min(d(+)(u), d(-)(v)} for all pairs u and v of vertices in D. Let delta(D) be the minimum degree of D. We call a graph or digraph D maximally edge-connected when lambda(D) =delta(D) and maximally local- edge-connected when lambda(u, v) = min {d(+)(u), d(-)(v)} for all pairs u and v of vertices in D. In this paper we show that some known sufficient conditions that guarantee equality of lambda(D) and minimum degree delta(D) for an oriented graph D also guarantee that D is maximally local-edge-connected. In addition, we generalize a result by Fabrega and Fiol [Bipartite graphs and digraphs with maximum connectivity, Discrete Appl. Math. 69 (1996) 271-279] that each bipartite digraph of diameter at most three is maximally edge-connected. (c) 2007 Elsevier B.V. All rights reserved.