Edge-disjoint paths and cycles in n-edge-connected graphs |
| |
Authors: | Andreas Huck |
| |
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). |
| |
Keywords: | |
|
|