Extra edge connectivity and isoperimetric edge connectivity |
| |
Authors: | Zhao Zhang |
| |
Institution: | a College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, PR China b Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, PR China |
| |
Abstract: | 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 λk(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γk(G) is defined as , where ω(U) is the number of edges with one end in U and the other end in . Write βk(G)=min{ω(U):U⊂V(G),|U|=k}. A graph G with 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. |
| |
Keywords: | Extra edge connectivity Isoperimetric edge connectivity |
本文献已被 ScienceDirect 等数据库收录! |
|