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.
展开▼
机译：如果阶n的图包含从3到n的所有长度的循环，则称其为全圈图。令G为哈密顿图，令x和y为在G的某个哈密顿循环上连续的G的顶点。Hakimi和Schmeichel证明（J Combin Theory Ser B 45：99–107，1988），如果d（x）+ d（y）≥n，则G是全环的，G具有除n − 1以外的所有长度的环，或者G是完全同构图的同构。在本文中，我们研究了哈密顿图G中各种长度的循环的存在，因为存在一对具有高和度但在G中的任何哈密顿循环上不相邻的顶点。
展开▼
