# From edge-disjoint paths to independent paths

Let $\mathcal{G}_k$ denote the set of all graphs that contain two vertices $x,y$ and $k$ edge-disjoint $x-y$ paths.

Define $f(k)$ to be the maximum such that for every graph $G\in \mathcal{G}_k$ there are two vertices $x',y'$ with $f(k)$ independent $x'-y'$ paths in $G$.

Here, a set of paths is independent if none contains an internal vertex of another.

Are any lower bounds for $f(k)$ known in the literature?

In particular, I need $f(3)=3$ in an algorithm where I need to find some obstructions in a graph. This is not hard to prove, but I'm wondering whether it is known in the literature, maybe as a special case of a more general theorem.

As a different formulation, how large can you make $f(k)$ in the following statement?

If $G$ is an undirected graph containing two vertices $x,y$ and $k$ edge-disjoint $x-y$ paths, then $G$ contains two vertices $x',y'$ with $f(k)$ independent $x'-y'$ paths.

-

3
$f(k)$ is a maximum of what? What quantity does it denote? – Shir Feb 10 '12 at 22:30
Some doubts: in a graph $G \in \mathcal{G}_k$, are other non $k$ edge-disjoint paths allowed between $x$ and $y$? A graph $G \in \mathcal{G}_k$ must contain at least one pair of vertices $x$ and $y$ connected with $k$ disjoint edges? or exactly one pair? What about a graph that contais a pair of vertices connected with $k$ disjoint edges and also a pair of vertices connected with $k+1$ disjoint edges? – Marzio De Biasi Feb 10 '12 at 23:16
Apologies, I corrected the definition of $f(k)$. – Serge Gaspers Feb 10 '12 at 23:51

2
I could be mistaken but it seems that the well-known series parallel graph (the recursive diamond graph, see cseweb.ucsd.edu/~dasgupta/254-embeddings/claire.pdf) can be used to show that $f(k) = 2$ for any value of $k$. – Chandra Chekuri Feb 12 '12 at 15:00
@ChandraChekuri: Actually, for the diamond graph $G_2$, we have two vertices $s,t$ with $4$ edge-disjoint $s-t$ paths, but we have 3 independent $x'-y'$ paths, where $x'=s$ and $y'$ is one of the 2 degree-4 vertices besides $s$ and $t$. I believe that these graphs can be used, though, to show that $f(k)=3$ for any $k\ge 3$. – Serge Gaspers Feb 12 '12 at 16:07
show 1 more comment

## 1 Answer

It turns out that $f(k)=3$ for all $k\ge 3$. Recursive diamond graphs are extremal. See arXiv:1203.4483 for a proof.

-

2
yippee. a cstheory.SE citation :) – Suresh Venkat♦ Mar 21 '12 at 16:49
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 48, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9246264100074768, "perplexity_flag": "head"}