On the 3-restricted edge connectivity of permutation graphs
On the 3-restricted edge connectivity of permutation graphs
复制标题
DOI：
10.1016/j.dam.2008.04.010
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
C. Balbuena;Diego González-Moreno;X. Marcote
中科院分区：
文献类型：
--
作者：
C. Balbuena;Diego González-Moreno;X. Marcote
一个连通图G的边割W是k-限制边割，如果G-W是不连通的，并且G-W的每个分支至少有k个顶点。k-限制边连通度定义为所有k-限制边割上的最小基数。置换图是通过取图的两个不相交的副本并在两个副本之间添加完美匹配来获得的。置换图的k-限制边连通度的上界是所谓的最小k-边度。本文给出了置换图的最优k-限制边连通度和超k-限制边连通度（k= 2，3）的一些充分条件.
An edge cut W of a connected graph G is a k-restricted edge cut if G−W is disconnected, and every component of G−W has at least k vertices. The k-restricted edge connectivity is defined as the minimum cardinality over all k-restricted edge cuts. A permutation graph is obtained by taking two disjoint copies of a graph and adding a perfect matching between the two copies. The k-restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum k-edge degree. In this paper some sufficient conditions guaranteeing optimal k-restricted edge connectivity and super k-restricted edge connectivity for permutation graphs are presented for k=2,3.