Graph connectivity after path removal (Q1878600): Difference between revisions

A subset \(S\) of the vertices of a graph \(G\) is called non-separating if \(G\setminus S \) is connected. \textit{C. Thomassen} [J. Graph Theory 5, 351-354 (1981; Zbl 0498.05044)] proved that if \(G\) is a \((k+3)\)-connected graph, then \(G\) contains a cycle, such that \(G\setminus V(C)\) is \(k\)-connected. The authors sharpen this result in the following way: If \(\alpha(k) \) denotes the minimum number such that in every \(\alpha(k)\) connected graph \(G\) for all \(u,v\in V(G)\) there are \(k\) vertex-disjoint \(u\)-\(v\) paths, then \(\alpha(k)\leq 22k+2\). It was known earlier that \(\alpha(1)=\alpha(2) =3\), in the paper it is shown that \(\alpha(3)=6\). The authors make another step in answering the following conjecture of Lovász: For each natural number \(k\), there exists a least natural number \(\beta(k)\) such that, for any two vertices \(u,v\) in any \(\beta \)-connected graph \(G\), there exists a \(u\)-\(v\) path \(P\) such that \(G\setminus V(P)\) is \(k\)-connected. Namely, they show that \(\beta(2)=5\).