Non-separating subgraphs after deleting many disjoint paths (Q618034): Difference between revisions

The following conjecture is raised in the paper: There exists a function \(f=f(k,l)\) such that for every \(f(k,l)\)-connected graph \(G\) and for every distinct vertices \(s\) and \(t\) in \(G\), there are \(k\) internally disjoint paths \(P_{1},\dots,P_{k}\) with endpoints \(s\) and \(t\) such that \(G-\bigcup_{i=1}^{k} V(P_{i})\) is \(l\)-connected. Setting \(k=1\) reduces the problem to a conjecture of Lovász that has been settled for \(l=1,2.\) The authors generalize some known results by showing that \(f(k,1)=2k+1\), the value \(2k+1\) being the best possible, and \(f(k,2)\leq 3k+2\).