Consider the following property of an undirected graph: For any four distinct vertices $a,b,c,d$, there is a path from $a$ to $b$ and a path from $c$ to $d$ such that the two paths do not share any vertex.

Is there a name for this property, or has it been studied? It looks related to vertex connectivity but not quite the same. Also it seems that any graph satisfying this property must have vertex connectivity at least $2$.

  • 1
    $\begingroup$ Wouldn't the vertex connectivity have to be at least $3$? If the graph $G$ can be disconnected by removing two vertices $a,b$, and if $c,d$ are in different components of $G-a-b$ $\endgroup$ – bof Apr 5 '19 at 9:43

The property that you are describing is called $2$-linked. More generally, we say that a graph is $k$-linked if it has at least $2k$ vertices and for all distinct vertices $s_1, \dots s_k, t_1, \dots, t_k$ there are $k$-vertex disjoint paths connecting $s_i$ to $t_i$ for all $i \in [k]$. Note that every $k$-linked graph is $k$-connected. The converse is not true. For example, a cycle is $2$-connected but is not $2$-linked.

However, it is a classic theorem that there is a function $f(k)$ such that every $f(k)$-connected graph is $k$-linked. The current best bound for $f(k)$ is due to Thomas and Wollan, where they prove that every $10k$-connected graph is $k$-linked. The paper is titled An improved linear edge bound for graph linkages, and is available for free on Robin Thomas' webpage.

| cite | improve this answer | |
  • $\begingroup$ Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper. $\endgroup$ – user137930 Apr 5 '19 at 11:06
  • $\begingroup$ Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124 $\endgroup$ – Tony Huynh Apr 5 '19 at 11:11
  • $\begingroup$ Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear. $\endgroup$ – user137930 Apr 5 '19 at 11:32
  • $\begingroup$ Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, \dots, s_k, t_1, \dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked. $\endgroup$ – Tony Huynh Apr 5 '19 at 11:59
  • $\begingroup$ It's obvious that your new definition (where vertices are not necessarily distinct) implies the original one, but why are the two equivalent? $\endgroup$ – user137930 Apr 5 '19 at 12:36

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.