Liftings in finite graphs and linkages in infinite graphs with prescribed edge-connectivity.

*(English)*Zbl 1353.05074Summary: 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.

##### MSC:

05C40 | Connectivity |

PDF
BibTeX
XML
Cite

\textit{S. Ok} et al., Graphs Comb. 32, No. 6, 2575--2589 (2016; Zbl 1353.05074)

Full Text:
DOI

##### References:

[1] | Aharoni, R; Thomassen, C, Infinite, highly connected digraphs with no two arc-disjoint spanning trees, J. Graph Theory, 13, 71-74, (1989) · Zbl 0665.05023 |

[2] | Chan, YH; Fung, WS; Lau, LC; Yung, CK, Degree bounded network design with metric costs, SIAM J. Comput., 40, 953-980, (2011) · Zbl 1235.05078 |

[3] | Frank, A, On a theorem of mader, Ann. Disc. Math., 101, 49-57, (1992) · Zbl 0789.05051 |

[4] | Huck, A, A sufficient condition for graphs to be weakly \(k\)-linked, Graphs Comb., 7, 323-351, (1991) · Zbl 0780.05036 |

[5] | Mader, W, A reduction method for edge-connectivity in graphs, Ann. Disc. Math., 3, 145-164, (1978) · Zbl 0389.05042 |

[6] | Okamura, H, Every \(4k\)-edge-connected graph is weakly-\(3k\)-linked, Graphs Comb., 6, 179185, (1990) · Zbl 0708.05036 |

[7] | Thomassen, C, 2-linked graphs, Eur. J. Comb., 1, 371-378, (1980) · Zbl 0457.05044 |

[8] | Thomassen C.: Orientations of infinite graphs with prescribed edge-connectivity. Combinatorica (2016). doi:10.1007/s00493-015-3173-0 · Zbl 1399.05139 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.