No label defined (Q4374722)

The paper extends results of the authors published in [Discrete Math. 133, No. 1-3, 319-324 (1994; Zbl 0824.05045)]. The main theorem says that a simple connected graph \(G\) of order \(n\), connectivity \(k\geq 2\) and independence number \(\alpha \) is Hamiltonian, provided each independent set \(S\) of size \(k+1\) satisfies one of the following conditions: \parskip =0pt \parindent =20pt \begin{itemize} \item[(a)] there exists \(t\leq k\) such that \({|}N(X){|}\geq \min \{(t(n-1)+1)/(t+1),n-\delta (G)\}\) for every \(X\subset S\) of size \(t\), or \item [(b)] \(\deg(u)+\deg(v)\geq n\) for some \(u\neq v\in S\), or \item [(c)] \({|}N(u)\cap N(v){|}\geq \alpha \) for some \(u\neq v\in S\), or \item [(d)] \({|}N(u)\cup N(v){|}\geq n-k\) for some \(u\neq v\in S\), or \item [(e)] there exist distinct \(u,v\in S\) such that \(\max \{\deg(x),\deg(y)\}\geq n/2\) for any \(x\in \{u,v\}\) and any \(y\) such that \(d(x,y)=2\). \parindent =0pt (Here \(\delta (G)\) stands for the minimum degree in \(G\), \(N(u)\) is the open neighborhood of \(u\) and \(d(x,y)\) is the distance of vertices \(x\) and \(y\).) This theorem generalizes and unifies a number of previously known sufficient conditions for Hamiltonicity of graphs. An interesting feature of the theorem is that different pairs of vertices are allowed to satisfy different conditions.\end{itemize}