共 10 条
Two paths joining given vertices in 2k-edge-connected graphs
被引:2
|作者:
Okamura, H
[1
]
机构:
[1] Konan Univ, Dept Informat Sci & Syst Engn, Kobe, Hyogo 6588501, Japan
关键词:
k-edge-connected;
disjoint;
2;
paths;
2-reducible;
D O I:
10.1007/s00373-005-0626-z
中图分类号:
O1 [数学];
学科分类号:
0701 ;
070101 ;
摘要:
Let k >= 2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X subset of V(G), e(X) denotes the number of edges between X and V(G) - X. Let {s(i), t(i)} subset of X-i subset of (G) (i=1,2) and X-1 boolean AND X-2= 0. We here prove that if k is even and e(X-i) <= 2k-1 (i=1,2), then there exist paths P-1 and P-2 such that P-i joins s(i) and t(i), V(P-i) subset of X-i (i=1,2) and G - E(P-1 boolean OR P-2) is (k-2)-edge-connected (for odd k, if e(X-1) <= 2k-2 and e(X-2) <= 2k-1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.
引用
收藏
页码:503 / 514
页数:12
相关论文