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

Improve this question
$\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
    Commented Apr 5, 2019 at 9:43

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Apr 5, 2019 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
    Commented Apr 5, 2019 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
    Commented Apr 5, 2019 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
    Commented Apr 5, 2019 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
    Commented Apr 5, 2019 at 12:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .