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]

The classical Ore's Theorem states that every graph G of order n ≥ 3 with σ 2 (G) ≥ n is hamiltonian, where σ 2 (G) = min { d G (x) + d G (y) : x , y ∈ V (G) , x ≠ y , x y ∉ E (G) }. Recently, Ferrara, Jacobson and Powell (Discrete Math. 312 (2012), 459–461) extended the Moon–Moser Theorem and characterized the non-hamiltonian balanced bipartite graphs H of order 2 n ≥ 4 with partite sets X and Y satisfying σ 1 , 1 (H) ≥ n , where σ 1 , 1 (H) = min { d H (x) + d H (y) : x ∈ X , y ∈ Y , x y ∉ E (H) }. Though the latter result apparently deals with a narrower class of graphs, we prove in this paper that it implies Ore's Theorem for graphs of even order. [ABSTRACT FROM AUTHOR]