Vertex-disjoint cycles containing specified vertices in a graph (Q2508413)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Vertex-disjoint cycles containing specified vertices in a graph
scientific article

    Statements

    Vertex-disjoint cycles containing specified vertices in a graph (English)
    0 references
    0 references
    0 references
    12 October 2006
    0 references
    In this long paper the authors achieve as a main result that for graphs \(G= (V,E)\) satisfying the Ore condition, i.e. the sum of degrees of two of two nonadjacent distinct vertices of \(G\) is greater or equal to \(|V|\), the existence of \(k\) vertex-disjoint cycles \(C_1,\dots, C_k\) of \(G\) with \(\sum^k_{i=1} |V(C_i)| \geq 3,99\,k\) and a \(k\)-vertex set \(V' \subseteq V\) with \(|V'\cap V(C_i)|= 1\) for \(i= 1,\dots,k\) implies the existence of \(k\) vertex-disjoint cycles \(D_1,\dots, D_k\) such that \(\bigcup^k_{i=1} V(D_i) = V\) and \(|V'\cap V(D_i)|= 1\) for \(i= 1,\dots,k\).
    0 references
    0 references
    0 references
    0 references
    0 references
    vertex-disjoint cycle
    0 references
    specified vertices
    0 references
    degree sum condition
    0 references
    Ore type condition
    0 references