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
相关论文
共 10 条
  • [1] 2-Reducible Two Paths and an Edge Constructing a Path in (2k+1)-Edge-Connected Graphs
    Okamura, Haruko
    GRAPHS AND COMBINATORICS, 2010, 26 (04) : 571 - 589
  • [2] 2-Reducible Two Paths and Two Edges Constructing a Cycle in (2k+1)-Edge-Connected Graphs
    Okamura, Haruko
    GRAPHS AND COMBINATORICS, 2025, 41 (02)
  • [3] Vertices of degree k in a minimally k-edge-connected digraph
    Yuan, XD
    Cai, MC
    DISCRETE MATHEMATICS, 2000, 218 (1-3) : 293 - 298
  • [4] Connectivity Keeping Paths in k-Connected Graphs
    Mader, W.
    JOURNAL OF GRAPH THEORY, 2010, 65 (01) : 61 - 69
  • [5] The number of vertices of degree k in a minimally k-edge-connected digraph
    Yuan, XD
    Kang, LY
    Cai, MC
    JOURNAL OF GRAPH THEORY, 2000, 33 (02) : 94 - 108
  • [6] Connectivity keeping paths in k-connected bipartite graphs
    Luo, Lian
    Tian, Yingzhi
    Wu, Liyun
    DISCRETE MATHEMATICS, 2022, 345 (04)
  • [7] Extremal problems on saturation for the family of k-edge-connected graphs
    Lei, Hui
    Suil, O.
    Shi, Yongtang
    West, Douglas B.
    Zhu, Xuding
    DISCRETE APPLIED MATHEMATICS, 2019, 260 : 278 - 283
  • [8] Proof of a conjecture on connectivity keeping odd paths in k-connected bipartite graphs ☆
    Yang, Qing
    Tian, Yingzhi
    DISCRETE MATHEMATICS, 2025, 348 (08)
  • [9] Monochromatic connected matchings in 2-edge-colored multipartite graphs
    Balogh, Jozsef
    Kostochka, Alexandr
    Lavrov, Mikhail
    Liu, Xujun
    JOURNAL OF GRAPH THEORY, 2022, 100 (03) : 578 - 607
  • [10] 2-edge-Hamiltonian-connectedness of 4-connected plane graphs
    Ozeki, Kenta
    Vrana, Petr
    EUROPEAN JOURNAL OF COMBINATORICS, 2014, 35 : 432 - 448