zbMATH — the first resource for mathematics

A sufficient condition for Hamiltonian graphs. (English) Zbl 0838.05078
The following generalization of Ore’s sufficient condition for Hamiltonian graphs is proved. For a pair of non-adjacent vertices \(u\) and \(v\) of a simple graph \(G\) let \(\omega(u, v)\) be the number of components of the subgraph induced by the neighbours of \(u\) that contain no neighbour of \(v\). Let \(\pi(u, v)= \max\{\omega(u, v), \omega(v, u)\}\). If in a graph \(G\) of order \(n\) any pair \(u\), \(v\) of non-adjacent vertices satisfies \(\text{deg}(u)+ \text{deg}(v)+ \pi(u, v)\geq n\), then \(G\) is Hamiltonian.
05C45 Eulerian and Hamiltonian graphs
Full Text: EuDML
[1] ASRATYAN A. S., KHACHATRYAN N. K.: Two theorems on hamiltonian graphs. Mat. Zametki 35 (1984), 55-61. · Zbl 0552.05038
[2] FAUDREE R. J., GOULD R. J., JACOBSON R. S., SCHELP R. H.: Neighborhood unions and hamiltonian properties in graphs. J. Combin. Theory Ser. B 46 (1989), 1-20. · Zbl 0677.05056
[3] FRAISSE P.: A new sufficient condition for hamiltonian graphs. J. Graph Theory 10 (1986), 405-409. · Zbl 0606.05043
[4] GOULD R. J.: Updating the hamiltonian problem - a survey. J. Graph Theory 15 (1991), 121-157. · Zbl 0746.05039
[5] ORE O.: Note on hamiltonian circuits. Amer. Math. Monthly 67 (1960), 5. · Zbl 0089.39505
[6] TIAN F.: A note on the paper ”A new sufficient condition for hamiltonian graphs”. Preprint, 1989.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.