×

An improvement of Bondy’s theorem on Hamilton graph condition. (English) Zbl 0986.05068

Let \(G= (V,E)\) be a graph. \(\sigma_k(G)\) is the minimum of the degree sum of every independent set of order \(k\) in \(G\). It is proved in this paper that a \(k\)-connected tough graph of order \(n\) contains a Hamilton circuit if \(\sigma_{k+1}(G)\) is at least \((k+1)(n-3)/2\). This result strengthens an early result of Bondy in 1980.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
PDFBibTeX XMLCite