Local-Restricted-Edge-Connectivity of Graphs

Abstract

The local-restricted-edge-connectivity \(\lambda'(e, f)\) of two nonadjacent edges \(e\) and \(f\) in a graph \(G\) is the maximum number of edge-disjoint \(e\)-\(f\) paths in \(G\). It is clear that \(\lambda'(G) = \min\{\lambda'(e, f) \mid e \text{ and } f \text{ are nonadjacent edges in } G\}\), and \(\lambda'(e, f) \leq \min\{\xi(e), \xi(f)\}\) for all pairs \(e\) and \(f\) of nonadjacent edges in \(G\), where \(\lambda(G)\), \(\xi(e)\), and \(\xi(f)\) denote the restricted-edge-connectivity of \(G\), the edge-degree of edges \(e\) and \(f\), respectively. Let \(\xi(G)\) be the minimum edge-degree of \(G\). We call a graph \(G\) optimally restricted-edge-connected when \(\lambda'(G) = \xi(G)\) and optimally local-restricted-edge-connected if \(\lambda'(e, f) = \min\{\xi(e),\xi(f)\}\) for all pairs \(e\) and \(f\) of nonadjacent edges in \(G\). In this paper, we show that some known sufficient conditions that guarantee that a graph is optimally restricted-edge-connected also guarantee that it is optimally local-restricted-edge-connected.