scientific article; zbMATH DE number 1109411

From MaRDI portal
Publication:4374722





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}











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4374722)