For which $m,n \in \mathbb N_+$ with $m \leq n$ and $n$ large exist $n$-connected graphs which are not $m$-linked?

48 Views Asked by At

The question is only interesting if we search for $n$ as large as possible.

Recall: A graph $G$ is $m$-linked iff for every set of $2 m$ distinct vertices $s_1, ..., s_m, t_1,...,t_m$ in $G$ there exist disjoint paths $P_1,...,P_m$ in $G$ such that the endpoints of $P_\ell$ are $s_\ell$ and $t_\ell$. This ist much more than being just $m$-connected.

$G_2, H_2$ are not $2$-linekd, $H_3$ is not $3$.linked, $G_4$ is not $4$-linked

I found a very simple example and would like to know if someone can offer more.

Let $r \in \mathbb N$ with $r > 1$ and $V(K^{2 \cdot r}) = \{1,...,r,r+1,...,2\cdot r\}$. Define $G_r := K^{2 \cdot r} - \{\{1, 2\}, \{3, 4\}, ..., \{2\cdot r-1, 2 \cdot r\}\}$ as the complete graph missing $r$ special edges. Then, $G_r$ is not $r$-linked but still $(2 \cdot r - 2)$-connected.

Let $H_r := G_r \odot K^{r-1}$. Note that $\odot$ means the "join" (also known as "Zykov sum": The Zykov sum of two graphs with disjoint vertex sets is formed by taking the union of the two graphs and adding all edges between the graphs). Then, $H_r$ is still not $r$-linked but it is $(3 \cdot r - 3)$-connected. For vividness consider the picture above.