zbMATH — the first resource for mathematics

Every 4k-edge-connected graph is weakly 3k-linked. (English) Zbl 0708.05036
A graph is weakly k-linked, if for every k pairs of vertices $$(s_ i,t_ i)$$ there exist k edge-disjoint paths $$P_ i$$ such that $$P_ i$$ joins $$s_ i$$ and $$t_ i$$ (1$$\leq i\leq k)$$. Let be g(k) the minimum of the edge connectivity numbers such that for each graph G which is g(k) edge connected holds: G is weakly k-linked. C. Thomassen [Eur. J. Comb. 1, 371-378 (1980; Zbl 0457.05044)] conjectured that $$g(2k+1)=g(2k)=2k+1$$ (k$$\geq 1)$$. Here the author proves g(3k)$$\leq 4k$$ and $$g(3k+1)\leq g(3k+2)\leq 4k+2$$ (k$$\geq 2)$$.
Reviewer: M.Hager

MSC:
 05C40 Connectivity 05C38 Paths and cycles