6
$\begingroup$

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$.

$\endgroup$
1
  • 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
8
$\begingroup$

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 here.

$\endgroup$
8
  • $\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.