Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647929 | Discrete Mathematics | 2012 | 6 Pages |
Abstract
In 1980, Bondy proved that for an integer k≥2k≥2 a (k+s)(k+s)-connected graph of order n≥3n≥3 is traceable (s=−1s=−1) or Hamiltonian (s=0s=0) or Hamiltonian-connected (s=1s=1) if the degree sum of every set of k+1k+1 pairwise nonadjacent vertices is at least 12((k+1)(n+s−1)+1). This generalizes the well-known sufficient conditions of Dirac (k=0k=0) and Ore (k=1k=1). The condition in Bondy’s Theorem is not tight for k≥2k≥2. We improve this sufficient degree condition and show the general tightness of this result.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Arnfried Kemnitz, Ingo Schiermeyer,