Edge-Disjoint Paths Problem in Highly Connected, Infinite Graphs

Abstract

We construct for all $k\in \mathbb{N}$ a $k$-edge-connected digraph $D$ with $x_1,y_1,x_2,y_2\in V(D)$ such that there are no edge-disjoint $x_1 \rightarrow y_1$ and $x_2\rightarrow y_2$ paths. We also prove that contrary to the directed case, for undirected graphs, $(2n-1)$-edge-connectivity implies the linkability of arbitrary $n$ terminal pairs with edge-disjoint paths.

Bibtex entry:

@techreport{egres-14-10,
AUTHOR = {Jo{\'o}, Attila},
TITLE = {Edge-Disjoint Paths Problem in Highly Connected, Infinite Graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2014},
NUMBER = {TR-2014-10}
}