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 = \emptyset\), \(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 = \emptyset, 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).