Cycle Lengths in Hamiltonian Graphs with a Pair of Vertices Having Large Degree Sum |
| |
Authors: | Michael Ferrara Michael S. Jacobson Angela Harris |
| |
Affiliation: | 1. University of Colorado Denver, Denver, CO, 80217, USA 2. University of Wisconsin, Whitewater, Whitewater, WI, 53190, USA
|
| |
Abstract: | A graph of order n is said to be pancyclic if it contains cycles of all lengths from three to n. Let G be a Hamiltonian graph and let x and y be vertices of G that are consecutive on some Hamiltonian cycle in G. Hakimi and Schmeichel showed (J Combin Theory Ser B 45:99–107, 1988) that if d(x) + d(y) ≥ n then either G is pancyclic, G has cycles of all lengths except n − 1 or G is isomorphic to a complete bipartite graph. In this paper, we study the existence of cycles of various lengths in a Hamiltonian graph G given the existence of a pair of vertices that have a high degree sum but are not adjacent on any Hamiltonian cycle in G. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|