Edge‐disjoint paths and cycles in n‐edge‐connected graphs
Andreas Huck · Journal of Graph Theory · 1992
Abstract We consider finite undirected loopless graphs G in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal n ≥ 0 with the following property: If G is an n‐edge‐connected graph, s1, ⃛,sk, t1, ⃛,tk are vertices of G, and f1, ⃛,fl, g1, ⃛,gl, are pairwise distinct edges of G, then for each i = 1, ⃛, k there exists a path Pi in G, connecting si and ti and for each i = 1, ⃛,l there exists a cycle Ci in G containing fi and gi such that P1, ⃛,Pk, C1, ⃛, Cl are pairwise edge‐disjoint. We give upper and lower bounds for g(k, l).