Local Restricted Edge Connectivity and Restricted Edge-Connectivity of Graphs

Abstract

Let $G$ be a connected graph and $k>1$ be an integer. The local $k$-restricted edge connectivity ${\lambda }_k(X,Y)$ of $X,Y$ in $G$ is the maximum number of edge-disjoint $X$-$Y$ paths for $X,Y\subseteq V$ with $|X|=|Y|=k$, $X\cap Y=\mathrm{\varnothing }$, $G[X]$ and $G[Y]$ are connected. The $k$-restricted edge connectivity of $G$ is defined as ${\lambda }_k(G)=min\{{\lambda }_k(X,Y):X,Y\subseteq V,|X|=|Y|=k,X\cap Y=\mathrm{\varnothing },G[X]\text{ and }G[Y]$ are connected. Then $G$ is local optimal $k$-restricted edge connected if ${\lambda }_k(X,Y)=min\{w(X),w(Y)\}$ for all $X,Y\subseteq V$ with $|X|=|Y|=k$, $G[X]$ and $G[Y]$ are connected, where $w(X)=|E(X,\overline{X})|$. If ${\lambda }_k(G)={\xi }_k(G)$, where ${\xi }_k(G)=min\{w(X):U\subset V,|U|=k\text{ and }G[U]\text{ is connected}\}$, then $G$ is called ${\lambda }_k$-optimal. In this paper, we obtain several sufficient conditions for a graph to be $3$-optimal (or local optimal $k$-restricted edge connected).