scientific article; zbMATH DE number 1109411
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}
- Some localization Hamiltonian conditions
- One criterion of existence of a Hamiltonian cycle
- A common generalization of Chvátal-Erdös' and Fraisse's sufficient conditions for hamiltonian graphs
- Independent sets, cliques and hamiltonian graphs
- scientific article; zbMATH DE number 4164899 (Why is no real title available?)
- A new sufficient condition for hamiltonian graphs
- scientific article; zbMATH DE number 4043882 (Why is no real title available?)
- scientific article; zbMATH DE number 2058271 (Why is no real title available?)
- scientific article; zbMATH DE number 2114048 (Why is no real title available?)
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)