Liftings in Finite Graphs and Linkages in Infinite Graphs with Prescribed Edge-Connectivity

被引:2
作者
Ok, Seongmin [1 ]
Richter, R. Bruce [2 ]
Thomassen, Carsten [1 ]
机构
[1] Tech Univ Denmark, Dept Appl Math & Comp Sci, Copenhagen, Denmark
[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
Edge-connectivity; Lifting;
D O I
10.1007/s00373-016-1724-9
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph and let s be a vertex of G. We consider the structure of the set of all lifts of two edges incident with s that preserve edge-connectivity. Mader proved that two mild hypotheses imply there is at least one pair that lifts, while Frank showed (with the same hypotheses) that there are at least (deg(s)-1)/2 disjoint pairs that lift. We consider the lifting graph: its vertices are the edges incident with s, two being adjacent if they form a liftable pair. We have three main results, the first two with the same hypotheses as for Mader's Theorem. (i) Let F be a subset of the edges incident with s. We show that F is independent in the lifting graph of G if and only if there is a single edge-cut C in G of size at most r + 1 containing all the edges in F, where r is the maximum number of edge-disjoint paths from a vertex (not s) in one component of G - C to a vertex (not s) in another component of G - C. (ii) In the k-lifting graph, two edges incident with s are adjacent if their lifting leaves the resulting graph with the property that any two vertices different from s are joined by k pairwise edge-disjoint paths. If both deg(s) and k are even, then the k-lifting graph is a connected complete multipartite graph. In all other cases, there are at most two components. If there are exactly two components, then each component is a complete multipartite graph. If deg(s) is odd and there are two components, then one component is a single vertex. (iii) Huck proved that if k is odd and G is (k + 1)-edge-connected, then G is weakly k-linked (that is, for any k pairs {x(i), y(i)}, there are k edge-disjoint paths P-i, with P-i joining x(i) and y(i)). We use our results to extend a slight weakening of Huck's theorem to some infinite graphs: if k is odd, every (k + 2)-edge-connected, locally finite, 1-ended, infinite graph is weakly k-linked.
引用
收藏
页码:2575 / 2589
页数:15
相关论文
共 8 条
  • [1] INFINITE, HIGHLY CONNECTED DIGRAPHS WITH NO 2 ARC-DISJOINT SPANNING-TREES
    AHARONI, R
    THOMASSEN, C
    [J]. JOURNAL OF GRAPH THEORY, 1989, 13 (01) : 71 - 74
  • [2] DEGREE BOUNDED NETWORK DESIGN WITH METRIC COSTS
    Chan, Yuk Hei
    Fung, Wai Shing
    Lau, Lap Chi
    Yung, Chun Kong
    [J]. SIAM JOURNAL ON COMPUTING, 2011, 40 (04) : 953 - 980
  • [3] ON A THEOREM OF MADER
    FRANK, A
    [J]. DISCRETE MATHEMATICS, 1992, 101 (1-3) : 49 - 57
  • [4] A SUFFICIENT CONDITION FOR GRAPHS TO BE WEAKLY K-LINKED
    HUCK, A
    [J]. GRAPHS AND COMBINATORICS, 1991, 7 (04) : 323 - 351
  • [5] Mader W., 1978, Ann. Discrete Math, V3, P145
  • [6] Okamura H., 1990, GRAPHS COMB, V6
  • [7] Thomassen C., 1980, European Journal of Combinatorics, V1, P371
  • [8] Orientations of infinite graphs with prescribed edge-connectivity
    Thomassen, Carsten
    [J]. COMBINATORICA, 2016, 36 (05) : 601 - 621