Bound on m-restricted Edge Connectivity

An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restricted edge connectivity λ _m is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let ∂(X) denote the number of edges with one end in X and the other not in X and ξ _m = min{∂(X) : X is a connected vertex-induced subgraph of order m}. It is proved in this paper that if G has girth at least m/2+ 2, then λ _m ≤ ξ _m . The upper bound of λ _m is sharp. Supported by National Natural Science Foundation of China (Grant No.10271105) and Doctoral Fund of Zhangzhou Normal College.