New sufficient condition for Hamiltonian graphs (Q2463936)

Let \(\alpha(G)\) and \(N(v)\) be the independence number of \(G\) and the neighborhood of \(v\) in \(G\), respectively. The main result of this paper is the following theorem. If \(G\) is a \(k\)-connected \((k\geq2)\) graph of order \(n\), and if \(\max\{\deg(v): v\in S\}\geq n/2\) for every independent set \(S\) of order \(k\), such that \(S\) has two distinct vertices \(x,y\) with \(1\leq| N(x)\cap N(y)| \leq\alpha(G)-1\), then \(G\) is Hamiltonian. This theorem unifies and extends several well-known sufficient conditions to assure the existence of a Hamiltonian cycle in a simple graph \(G\) of order \(n\geq3\), e.g. Dirac's, Ore's, Fan's and Chen's conditions. The authors also show that there exist Hamiltonian graphs satisfying the hypothesis of the theorem above but whose Hamiltonicity cannot be assured by any one of the above-mentioned conditions.