One sufficient condition for Hamiltonian graphs involving distances (Q1759263)

From MaRDI portal
scientific article
Language Label Description Also known as
English
One sufficient condition for Hamiltonian graphs involving distances
scientific article

    Statements

    One sufficient condition for Hamiltonian graphs involving distances (English)
    0 references
    0 references
    0 references
    0 references
    20 November 2012
    0 references
    \textit{Ø. Ore} [Am. Math. Mon. 67, 55 (1960; Zbl 0089.39505)] established the well-known degree condition which states that if the degree sum of every pair of non-adjacent vertices in an \(n\)-vertex graph \(G\) is at least \(n\), then \(G\) is Hamiltonian. In 1990 \textit{G. T. Chen} [J. Graph Theory 14, No. 4, 501--508 (1990; Zbl 0721.05043)] showed that if \(2|N(u) \cup N(v)| + deg(u) + deg(v) \geq 2n-1\) for all pairs of non-adjacent vertices in a \(2\)-connected graph of order \(n\), then the graph is Hamiltonian. In the paper under review, it is shown that if this condition holds for all pairs of vertices distance 2 apart (in a \(2\)-connected graph of order \(n\)), then the graph is also Hamiltonian.
    0 references
    Ore condition
    0 references
    neighborhood union and degree condition
    0 references
    Chen condition
    0 references
    distance 2
    0 references

    Identifiers