Non-separating subgraphs after deleting many disjoint paths (Q618034)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Non-separating subgraphs after deleting many disjoint paths
scientific article

    Statements

    Non-separating subgraphs after deleting many disjoint paths (English)
    0 references
    0 references
    0 references
    14 January 2011
    0 references
    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\).
    0 references
    0 references
    non-separating subgraphs
    0 references
    Lovász conjecture
    0 references
    0 references
    0 references