Name
Abstract | ||
|---|---|---|
Let G be a graph of order n, sigma(k) = min {SIGMA(i = 1)k d(upsilon(i)): {upsilon-1,..., upsilon(k)] is an independent set of vertices in G}, NC = min{\N(u) or N(upsilon)\: u-upsilon is-not-an-element-of E(G)} and NC2 = min {\N(u) or N(upsilon)\: d(u, upsilon) = 2}. Ore proved that G is hamiltonian if sigma-2 greater-than-or-equal-to n greater-than-or-equal-to 3, while Faudree et al. proved that G is hamiltonian if G is 2-connected and NC greater-than-or-equal-to 1/3 (2n - 1). It is shown that both results are generalized by a recent result of Bauer et al. Various other existing results in hamiltonian graph theory involving degree-sums or cardinalities of neighborhood unions are also compared in terms of generality. Furthermore, some new results are proved. In particular, it is shown that the bound 1/3(2n - 1) on NC in the result of Faudree et al. can be lowered to 1/3(2n - 3), which is best possible. Also, G is shown to have a cycle of length at least min{n, 2(NC2)} if G is 2-connected and sigma-3 greater-than-or-equal-to n + 2. A D(lambda)-cycle (D(lambda)-path) of G is a cycle (path) C such that every component of G - V(C) has order smaller than lambda. Sufficient conditions of Lindquester for the existence of Hamilton cycles and paths involving NC2 are extended to D(lambda)-cycles and D(lambda)-paths. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1016/0012-365X(91)90468-H | DISCRETE MATHEMATICS |
Keywords | Field | DocType |
discrete mathematics | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Graph property,Hamiltonian (quantum mechanics),Hamiltonian path,Cardinality,Independent set,Mathematics | Journal |
Volume | Issue | ISSN |
96 | 1 | 0012-365X |
Citations | PageRank | References |
20 | 2.13 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Douglas Bauer | 1 | 20 | 2.13 |
| Genghua Fan | 2 | 412 | 65.22 |
| Henk Jan Veldman | 3 | 56 | 5.83 |