Edge-disjoint paths and cycles in n-edge-connected graphs

✍ Scribed by Andreas Huck

• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 826 KB
• Volume: 16
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190160605

✦ Synopsis

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, s~1~, ⃛,s~k~, t~1~, ⃛,t~k~ are vertices of G, and f~1~, ⃛,f~l~, g~1~, ⃛,g~l~, are pairwise distinct edges of G, then for each i = 1, ⃛, k there exists a path P~i~ in G, connecting s~i~ and t~i~ and for each i = 1, ⃛,l there exists a cycle C~i~ in G containing f~i~ and g~i~ such that P~1~, ⃛,P~k~, C~1~, ⃛, C~l~ are pairwise edge‐disjoint. We give upper and lower bounds for g(k, l).