Name
Abstract | ||
|---|---|---|
The well-known Chvatal-Erdos theorem states that every graph G of order at least three with alpha(G) <= kappa(G) has a Hamiltonian cycle, where alpha(G) and kappa(G) are the independence number and the connectivity of G, respectively. Oberly and Sumner [J. Graph Theory, 3 (1979), pp. 351356] have proved that every connected, locally connected claw-free graph of order at least three has a Hamiltonian cycle. We study the connection of these two theorems. For x is an element of V(G), let B(x) denote the subgraph of G induced by the closed neighborhood of x. Then the theorem by Oberly and Sumner says that a connected graph G of order at least three satisfying alpha(B(x)) <= 2 <= kappa(B(x)) for every vertex x has a Hamiltonian cycle. The comparison of this theorem with the Chvatal-Erdos theorem leads us to suspect that the threshold 2 between alpha(B(x)) and kappa(B(x)) is not necessary. We say that G satisfies the local Chvatal-Erdos condition if alpha(B(x)) <= kappa(B(x)) holds for every vertex x in G. The second author conjectured that if the order of a connected graph G is at least three and satisfies the local Chvatal-Erdos condition, then G has a Hamiltonian cycle. In this paper, we support this conjecture by proving that under this assumption, G is 1-tough and has a 2-factor. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/12090037X | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
Chvatal-Erdos theorem,Hamiltonian cycle,2-factor,toughness,independence number,connectivity | Discrete mathematics,Graph,Combinatorics,Independence number,Kappa,Hamiltonian path,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 4 | 0895-4801 |
Citations | PageRank | References |
4 | 0.50 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| G. Chen | 1 | 32 | 8.36 |
| Akira Saito | 2 | 361 | 64.55 |
| Songling Shan | 3 | 20 | 9.16 |