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.展开更多
Restricted edge connectivity of a graph G is defined to be the minimum size |U| of a set U of edges such that G-U is disconnected and G-U contains no trivial component K1. The high order edge connectivity Ni, i1, is t...Restricted edge connectivity of a graph G is defined to be the minimum size |U| of a set U of edges such that G-U is disconnected and G-U contains no trivial component K1. The high order edge connectivity Ni, i1, is the number of edge outsets of size i. TO determine all Ni, i 1, for a general graph is NP-hard. In this paper, the authors evaluated the restricted edge connectivity and the high order edge connectivity Ni, 1 i -1, for any connected Abelian Cayley graphs explicitly.展开更多
基金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.
文摘Restricted edge connectivity of a graph G is defined to be the minimum size |U| of a set U of edges such that G-U is disconnected and G-U contains no trivial component K1. The high order edge connectivity Ni, i1, is the number of edge outsets of size i. TO determine all Ni, i 1, for a general graph is NP-hard. In this paper, the authors evaluated the restricted edge connectivity and the high order edge connectivity Ni, 1 i -1, for any connected Abelian Cayley graphs explicitly.
