Two new sufficient conditions for Hamilton-connected graphs

Abstract

LetG be a 3-connected graph withn vertices,σ 3(G)=min{Σ i=1 3 d(v i)|{v 1,v v 2,v 3} is an independent set ofG},NC(G)=min{|N(u)∪N(v)||{u,v}⊆V(G),uv∉E(G)},NC2(G)=min{|N(u)∪N(v)||{u,v}⊆V(G),d(u,v)=2} and α(G)=max{|I||I is an independent set inG}. In this paper, the main results are as follows: Theorem I. Ifσ 3(G)≥max{n+4,3α(G)+1}, thenG is Hamilton-connected. Theorem II. Ifσ 3(G)≥n+4 andNC2(G)≥1/2(n+1), thenG is Hamilton-connected. Theorems I and II are the best possible, and are incomparable in the sense that neither theorem implies the other.