New sufficient condition for Hamiltonian graphs

Let GG be a graph, and δ(G)δ(G) and α(G)α(G) be the minimum degree and the independence number of GG, respectively. For a vertex v∈V(G)v∈V(G), d(v)d(v) and N(v)N(v) represent the degree of vv and the neighborhood of vv in GG, respectively. A number of sufficient conditions for a connected simple graph GG of order nn to be Hamiltonian have been proved. Among them are the well known Dirac condition (1952) (δ(G)≥n2) and Ore condition (1960) (for any pair of independent vertices uu and vv, d(u)+d(v)≥nd(u)+d(v)≥n). In 1984 Fan generalized these two conditions and proved that if GG is a 2-connected graph of order nn and max{d(x),d(y)}≥n/2max{d(x),d(y)}≥n/2 for each pair of nonadjacent vertices x,yx,y with distance 2 in GG, then GG is Hamiltonian. In 1993, Chen proved that if GG is a 2-connected graph of order nn, and if max{d(x),d(y)}≥n/2max{d(x),d(y)}≥n/2 for each pair of nonadjacent vertices x,yx,y with 1≤|N(x)∩N(y)|≤α(G)−11≤|N(x)∩N(y)|≤α(G)−1, then GG is Hamiltonian. In 1996, Chen, Egawa, Liu and Saito further showed that if GG is a kk-connected graph of order nn, and if max{d(v):v∈S}≥n/2max{d(v):v∈S}≥n/2 for every independent set SS of GG with |S|=k|S|=k which has two distinct vertices x,y∈Sx,y∈S such that the distance between xx and yy is 2, then GG is Hamiltonian. In this paper, we generalize all the above conditions and prove that if GG is a kk-connected graph of order nn, and if max{d(v):v∈S}≥n/2max{d(v):v∈S}≥n/2 for every independent set SS of GG with |S|=k|S|=k which has two distinct vertices x,y∈Sx,y∈S satisfying 1≤|N(x)∩N(y)|≤α(G)−11≤|N(x)∩N(y)|≤α(G)−1, then GG is Hamiltonian.