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) \leq \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.