Cycles in k-connected graphs whose deletion results in a (k-2)-connected graph (Q1089006)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Cycles in k-connected graphs whose deletion results in a (k-2)-connected graph
scientific article

    Statements

    Cycles in k-connected graphs whose deletion results in a (k-2)-connected graph (English)
    0 references
    0 references
    1987
    0 references
    In [J. Graph Theory 5, 351-354 (1981; Zbl 0498.05044)] \textit{C. Thomassen} proved that for \(k\geq 4\), every k-connected graph contains an induced cycle C such that G-V(C) is (k-3)-connected, and conjectured that for \(k\geq 3\), every k-connected graph with girth at least 4 contains an induced cycle whose deletion results in a (k-2)-connected graph, and every k-connected graph with girth at least 5 contains an induced cycle whose deletion results in a (k-1)-connected graph. The second conjecture was settled affirmatively by \textit{C. Thomassen} and \textit{B. Toft} for \(k=3\) in J. Comb. Theory, Ser. B 31, 199-224 (1981; Zbl 0456.05039), where the case \(3\leq k\leq 4\) of the first conjecture was also settled. Here, the author proves the first conjecture for \(k\geq 5\).
    0 references
    0 references
    deletion of a cycle
    0 references
    connectivity of graphs
    0 references
    0 references