A mixed version of Menger's theorem |
| |
| Authors: | Yoshimi Egawa Atsushi Kaneko Makoto Matsumoto |
| |
| Affiliation: | (1) Department of Applied Mathematics, Science University of Tokyo, Shinjuku-ku, 162 Tokyo, Japan;(2) Department of Mathematics Faculty of Science and Technology, Keio University, 3-14-1, Hiyoshi, Kohokkuku, 223 Yokohama, Japan;(3) Resarch Institute for Mathematical Sciences, Kyoto University, Sakyo-ku, 606 Kyoto, Japan |
| |
| Abstract: | An(a, b)-n-fan means a union ofn internally disjoint paths. Menger's theorem states that a graphG has an(a, b)-n-fan if and only ifG isn-connected betweena andb. We show thatG contains  edge-disjoint(a, b)-n-fans if and only if for anyk withk 0min{n–1, |V(G)|–2} and for any subsetX ofV(G)-{a, b} with cardinalityk, G-X is (n-k)-edge-connected betweena andb. |
| |
| Keywords: | 05 C 40 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
