Extra edge connectivity and isoperimetric edge connectivity

AbstractAn 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 λk(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γk(G) is defined as γk(G)=min{ω(U):U⊂V(G),|U|⩾k,|U¯|⩾k}, where ω(U) is the number of edges with one end in U and the other end in U¯=V⧹U. Write βk(G)=min{ω(U):U⊂V(G),|U|=k}. A graph G with γj(G)=βj(G)(j=1,…,k) is said to be γk-optimal.In this paper, we first prove that λk(G)=γk(G) if G is a regular graph with girth g⩾k/2. Then, we show that except for K3,3 and K4, a 3-regular vertex/edge transitive graph is γk-optimal if and only if its girth is at least k+2. Finally, we prove that a connected d-regular edge-transitive graph with d⩾6ek(G)/k is γk-optimal, where ek(G) is the maximum number of edges in a subgraph of G with order k