On a 2-factor with a specified edge in a graph satisfying the Ore condition (Q1850026)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On a 2-factor with a specified edge in a graph satisfying the Ore condition
scientific article

    Statements

    On a 2-factor with a specified edge in a graph satisfying the Ore condition (English)
    0 references
    0 references
    0 references
    2 December 2002
    0 references
    Let \(k\) be an integer greater than one, and let \(G\) be a simple graph with at least \(4k+1\) vertices. In the paper, it is proved that if \(\sigma_2(G)\geq |V(G)|\), then for an edge \(e\) of \(G\), there exists a 2-factor with \(k\) cycles that contains \(e\), or \(|V(G)|\) is even and \(G\) has a vertex cover of size \(|V(G)|/2\) containing both endpoints of \(e\). Here \(\sigma_2(G)\) denotes the minimum degree sum for a pair of non-adjacent vertices.
    0 references
    0 references
    0 references
    2-factor
    0 references
    Ore type condition
    0 references
    a specified edge
    0 references