| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418827 | Discrete Applied Mathematics | 2009 | 6 Pages |
Abstract
An edge cut WW of a connected graph GG is a kk-restricted edge cut if G−WG−W is disconnected, and every component of G−WG−W has at least kk vertices. The kk-restricted edge connectivity is defined as the minimum cardinality over all kk-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 kk-restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum kk-edge degree. In this paper some sufficient conditions guaranteeing optimal kk-restricted edge connectivity and super kk-restricted edge connectivity for permutation graphs are presented for k=2,3k=2,3.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
C. Balbuena, D. González-Moreno, X. Marcote,