2020/01/02 by Choi, Ilkyoo, Kim, Jinha
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2001.00385
We say a graph G has a Hamiltonian path if it has a path containing all vertices of G. For a graph G, let σ2(G) denote the minimum degree sum of two nonadjacent vertices of G; restrictions on σ2(G) are known as Ore-type conditions. Given an integer t≥ 5, we prove that if a connected graph G on n vertices satisfies σ2(G)>t-3\over t-2n, then G has either a Hamiltonian path or an induced subgraph isomorphic to K1, t. Moreover, we characterize all n-vertex graphs G where σ2(G)=t-3\over t-2n and G has neither a Hamiltonian path nor an induced subgraph isomorphic to K1, t. This is an analogue of a recent result by Momège, who investigated the case when t=4.