A proof of an inequality concerning k-restricted edge connectivity
A proof of an inequality concerning k-restricted edge connectivity
复制标题
DOI：
10.1016/j.disc.2005.04.020
复制
发表时间：
2005-11
期刊：
影响因子：
--
通讯作者：
Zhao Zhang;Jinjiang Yuan
中科院分区：
文献类型：
--
作者：
Zhao Zhang;Jinjiang Yuan
连通图G的一个边子集S是一个k-限制边割，如果G-S是不连通的，并且G-S的每个分支至少有k个顶点。k-限制边连通度是最小k-限制边割的基数。本文证明了除了一类定义良好的图之外，对任意k <$δ（G）+1，连通图G的k-限制边割都存在，其中δ（G）是G的最小度.此外，我们还得到了k-限制边连通度的一个上界。
An edge subset S of a connected graph G is a k-restricted edge cut if G-S is disconnected, and every component of G-S has at least k vertices. The k-restricted edge connectivity is the cardinality of a minimum k-restricted edge cut. In this note, we show that except for a well-defined class of graphs, k-restricted edge cuts of a connected graph G exist for any k⩽δ(G)+1, where δ(G) is the minimum degree of G. Furthermore, we obtain an upper bound for k-restricted edge connectivity.