6
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ $f(k)$ is a maximum of what? What quantity does it denote? $\endgroup$ – Shir Feb 10 '12 at 22:30
  • $\begingroup$ 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? $\endgroup$ – Marzio De Biasi Feb 10 '12 at 23:16
  • $\begingroup$ Apologies, I corrected the definition of $f(k)$. $\endgroup$ – Serge Gaspers Feb 10 '12 at 23:51
  • 2
    $\begingroup$ 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$. $\endgroup$ – Chandra Chekuri Feb 12 '12 at 15:00
  • $\begingroup$ @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$. $\endgroup$ – Serge Gaspers Feb 12 '12 at 16:07
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ yippee. a cstheory.SE citation :) $\endgroup$ – Suresh Venkat Mar 21 '12 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.