Every 4k-edge-connected graph is weakly 3k-linked (Q920108): Difference between revisions

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. \textit{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)\).