Name
Abstract | ||
|---|---|---|
Let G be a k-regular 2-connected graph of order n. jackson proved that G is hamiltonian if n less than or equal to 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to 22/7k if G is 3-connected and k greater than or equal to 63. We improve both results by showing that G is hamiltonian if n less than or equal to 7/2k - 7 and G does not belong to a restricted class F of nonhamiltonian graphs of connectivity 2. To establish this result we obtain a variation of Woodall's Hopping Lemma and use it to prove that if n less than or equal to 7/2k - 7 and G has a dominating cycle (i.e., a cycle such that the vertices off the cycle constitute an independent set), then G is hamiltonian. We also prove that if n less than or equal to 4k - 3 and G is not an element of F, then G has a dominating cycle. For k greater than or equal to 4 it is conjectured that G is hamiltonian if n less than or equal to 4k and G is not an element of F. (C) 1996 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1996 | 3.3.CO;2-P" target="_self" class="small-link-text"10.1002/(SICI)1097-0118(199606)22:23.3.CO;2-P | Journal of Graph Theory |
Keywords | Field | DocType |
connected graph | Discrete mathematics,Graph,Combinatorics,Bound graph,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 2 | 0364-9024 |
Citations | PageRank | References |
5 | 0.53 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. J. Broersma | 1 | 266 | 33.68 |
| Jan van den Heuvel | 2 | 361 | 34.75 |
| B. Jackson | 3 | 111 | 20.87 |
| H. J. Veldman | 4 | 262 | 44.44 |