(1) Department of Mathematics, Zhangzhou Normal College, Fujian, 363000, China;(2) Department ofMathematics, Xiamen University, Xiamen, 361005, China
Abstract:
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.