Name
Abstract | ||
|---|---|---|
For a graph G and an integer k, denote by V(k) the set {v is-an-element-of V(G) \ d(v) greater-than-or-equal-to k}. Veldman proved that if G is a 2-connected graph of order n with n less-than-or-equal-to 3k - 2 and \V(k)\ less-than-or-equal-to k, then G has a cycle containing all vertices of V(k). It is shown that the upper bound k on \V(k)\ is close to best possible in general. For the special case k = DELTA(G), it is conjectured that the condition \V(k)\ less-than-or-equal-to k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n less-than-or-equal-to 2DELTA(G) + delta(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n less-than-or-equal-to 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1002/jgt.3190170311 | Journal of Graph Theory |
Keywords | Field | DocType |
maximum degree,upper bound,connected graph,regular graph | Topology,Discrete mathematics,Combinatorics,Vertex (geometry),Bound graph,Upper and lower bounds,Vertex (graph theory),Cycle graph,Regular graph,Degree (graph theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
17 | 3 | 0364-9024 |
Citations | PageRank | References |
1 | 0.41 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. J. Broersma | 1 | 266 | 33.68 |
| J. van den Heuvel | 2 | 31 | 4.28 |
| H. A. Jung | 3 | 47 | 7.07 |
| H. J. Veldman | 4 | 262 | 44.44 |