A note on Lovász removable path conjecture

Lovász conjectured that for any natural number $k$,there exists a smallest natural number $f(k)$ such that, for any twovertices $s$ and $t$ in any $f(k)$-connected graph $G$, there existsan $s$-$t$ path $P$ such that $G-V(P)$ is $k$-connected. Thisconjecture is proved only for $k\leq2$. Here, we strengthen theresult for $k=2$ as follows: for any integers $l>0$ and $m\geq0$,there exists a function $f(l,m)$ such that, for any distinctvertices $s,t,v_1,\ldots,v_m$ in any $f(l,m)$-connected graph $G$,there exist $l$ internally vertex disjoint $s$-$t$ paths$P_1,\ldots,P_l$ such that for any subset $I\subset\{1,\ldots,l\}$,$G-\cup_{i\in I} V(P_i)$ is 2-connected and$\{v_1,v_2,\ldots,v_m\}\subset V(G)-\cup_{1\leq i\leq l} V(P_i)$.

Full Text (PDF format)

Published 15 June 2011