Maximally Local-Edge-Connected Graphs and Digraphs

Abstract

The local-edge-connectivity $(u,v)$ of two vertices $u$ and $v$ in a graph or digraph $D$ is the maximum number of edge-disjoint $u-v$ paths in $D$, and the edge-connectivity of $D$ is defined as $\lambda (D)=min\{\lambda (u,v)|u,v\in V(D)\}$. Clearly, $\lambda (u,v)\le min\{d^{+}(u),d^{-}(v)\}$ for all pairs $u$ and $v$ of vertices in $D$. We call a graph or digraph $D$ maximally local-edge-connected when

$$\lambda (u,v)=min\{d^{+}(u),d^{-}(v)\}$$

for all pairs $u$ and $v$ of vertices in $D$.

Recently, Fricke, Oellermann, and Swart have shown that some known sufficient conditions that guarantee equality of $\lambda (G)$ and minimum degree $\delta (G)$ for a graph $G$ are also sufficient to guarantee that $G$ is maximally local-edge-connected.
In this paper we extend some results of Fricke, Oellermann, and Swart to digraphs and we present further sufficient conditions for
graphs and digraphs to be maximally local-edge-connected.