Extra Edge Connectivity and Isoperimetric Edge
Connectivity

Zhao Zhang
College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, P. R. China
Abstract     Full Text  PPT

An edge set $S$ of a connected graph $G$ is a $k$-extra edge cut, if $G-S$ is no longer connected, and each component of $G-S$ has at least $k$ vertices. The cardinality of a minimum $k$-extra edge cut, denoted by $\lambda_k(G)$, is the $k$-extra edge connectivity of $G$. The $k$-th isoperimetric edge connectivity $\gamma_k(G)$ is defined as $ \gamma_k(G)=\min\{\omega(U)\colon U\subset V(G),|U|\geq k,|\overline U|\geq k\}$, where $\omega(U)$ is the number of edges with one end in $U$ and the other end in $\overline U=V\setminus U$. Write $\beta_k(G)=\min\{\omega(U)\colon U\subset V(G),|U|=k\}$. A graph $G$ with $\gamma_j(G)=\beta_j(G)\ (j=1,\ldots,k)$ is said to be $\gamma_{\,k}$-optimal.

We proved (1) $\lambda_k(G)=\gamma_{\,k}(G)$ if $G$ is a regular graph with girth $g\geq k/2$. (2) A 3-regular vertex/edge transitive graph is $\gamma_k$-optimal if and only if its girth is at least $k+2$. (3) A connected $d$-regular edge-transitive graph with $d\geq 6e_k(G)/k$ is $\gamma_{\,k}$-optimal, where $e_k(G)$ is the maximum number of edges in a subgraph of $G$ with order $k$.