Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651147 | Discrete Mathematics | 2007 | 5 Pages |
Abstract
In 1960 Ore proved the following theorem: Let G be a graph of order n . If d(u)+d(v)⩾nd(u)+d(v)⩾n for every pair of nonadjacent vertices u and vv, then G is hamiltonian. In this note we strengthen Ore's theorem as follows: we determine the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore's condition) but still imply that the graph is hamiltonian. Some other sufficient conditions (i.e. Fan's condition) for hamiltonian graphs are strengthened as well.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ralph J. Faudree, Richard H. Schelp, Akira Saito, Ingo Schiermeyer,