Closures,cycles, and paths |
| |
| Authors: | Jochen Harant Arnfried Kemnitz Akira Saito Ingo Schiermeyer |
| |
| Affiliation: | 1. Institut für mathematiktechnische universit?t ilmenau, , Germany;2. Computational mathematics technische universit?t braunschweig 38 023 braunschweig, , Germany;3. Department of computer science nihon university, , Tokyo, 156‐8550 Japan;4. Institut für diskrete mathematik und algebratechnische universit?t bergakademie freiberg09 596 Freiberg, , Germany |
| |
| Abstract: | In 1960 Ore proved the following theorem: Let G be a graph of order n. If d(u) + d(v)≥n for every pair of nonadjacent vertices u and v, then G is hamiltonian. Since then for several other graph properties similar sufficient degree conditions have been obtained, so‐called “Ore‐type degree conditions”. In [R. J. Faudree, R. H. Schelp, A. Saito, and I. Schiermeyer, Discrete Math 307 (2007), 873–877], Faudree et al. strengthened Ore's theorem as follows: They determined 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. In this article we prove that for some other graph properties the corresponding Ore‐type degree conditions can be strengthened as well. These graph properties include traceable graphs, hamiltonian‐connected graphs, k‐leaf‐connected graphs, pancyclic graphs, and graphs having a 2‐factor with two components. Graph closures are computed to show these results. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 314–323, 2012 |
| |
| Keywords: | Hamiltonian hamiltonian‐connected traceable |
|
|
