×

Generalizing Bondy’s theorems on sufficient conditions for Hamiltonian properties. (English) Zbl 1229.05191

Summary: In [“Longest paths and cycles in graphs of high degree,” Research Report CORR 80-16, Department of Combinatorics and Optimiation, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada (1980)], J. A. Bondy proved that a \((k+s)\)-connected graph of order \(p\geq 3\) is traceable \((s=-1)\) or Hamiltonian \((s=0)\) or Hamiltonian-connected \((s=1)\) if the degree sum of every set of \(k+1\) pairwise nonadjacent vertices is at least \(\frac{1}{2}((k+ 1) (p+s -1)+1)\). We show that one can allow exceptional \((k+1)\)-sets violating this condition and still implying the considered property. We give upper bounds for the number of such ‘bad’ sets depending on the connectivity and the minimum degree of the graph.

MSC:

05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite