Local-Restricted-Edge-Connectivity of Graphs

Abstract

The local-restricted-edge-connectivity ${\lambda }^{\prime }(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 }^{\prime }(G)=min\{{\lambda }^{\prime }(e,f)\mid e\text{ and }f\text{ are nonadjacent edges in }G\}$, and ${\lambda }^{\prime }(e,f)\le 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 }^{\prime }(G)=\xi (G)$ and optimally local-restricted-edge-connected if ${\lambda }^{\prime }(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.