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
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