Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
One sufficient condition for Hamiltonian graphs involving distances - MaRDI portal

One sufficient condition for Hamiltonian graphs involving distances (Q1759263)

From MaRDI portal





scientific article; zbMATH DE number 6108803
Language Label Description Also known as
English
One sufficient condition for Hamiltonian graphs involving distances
scientific article; zbMATH DE number 6108803

    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