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 λ<SUB> m </SUB>is the c...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 λ<SUB> m </SUB>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 ξ<SUB> m </SUB>= 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 λ<SUB> m </SUB>≤ ξ<SUB> m </SUB>. The upper bound of λ<SUB> m </SUB>is sharp.展开更多
基金National Natural Science Foundation of China (Grant No.10271105) and Doctoral Fund of Zhangzhou Normal College.
文摘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 λ<SUB> m </SUB>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 ξ<SUB> m </SUB>= 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 λ<SUB> m </SUB>≤ ξ<SUB> m </SUB>. The upper bound of λ<SUB> m </SUB>is sharp.
