Search

For a graph G, define σ 2 (G) by σ 2 (G) = min { d G (x) + d G (y) : x , y ∈ V (G) , x ≠ y , x y ∉ E (G) } . If G is a bipartite graph with partite sets X and Y, we also define σ 1 , 1 (G) by σ 1 , 1 (G) = min { d G (x) + d G (y) : x ∈ X , y ∈ Y , x y ∉ E (G) } . Ore's theorem states that a graph of order n ≥ 3 with σ 2 (G) ≥ n contains a hamiltonian cycle and the Moon–Moser theorem states that a balanced bipartite graph G of order 2 n ≥ 4 with σ 1 , 1 (G) ≥ n + 1 contains a hamiltonian cycle. In Chen et al. (Discrete Math 343:Article No. 111663, 2020), we studied the relationship between Ore's theorem and the Moon–Moser theorem, and proved that the refinement of the Moon–Moser theorem given by Ferrara et al. (Discrete Math 312:459–461, 2012) implies Ore's theorem for graphs of even order. In this paper, we extend the above study to the graphs of odd order. Since no graphs of odd order contain a spanning balanced bipartite subgraph, the Moon–Moser theorem does not work in this case. We instead introduce its counterpart for the graphs in which the orders of the partite sets differ by 1, proved in Matsubara et al. (Discrete Math 340:87–95, 2017). We refine this result and prove that this refinement implies Ore's theorem. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]