Name
Abstract | ||
|---|---|---|
A number of results are established concerning long cycles in graphs with large degree sums. Let G be a graph on n vertices such that d ( x )+ d ( y )+ d ( z )⩾ s for all triples of independent vertices x , y , z . Let c be the length of a longest cycle in G and α the cardinality of a maximum independent set of vertices. If G is 1-tough and s ⩾ n , then every longest cycle in G is a dominating cycle and c⩾ min (n, n+ 1 3 s−α)⩾ min (n, 1 2 n+ 1 3 s)⩾ 5 6 n . If G is 2-connected and s ⩾ n +2, then also c⩾ min (n, n+ 1 3 s-α) , generalizing a result of Bondy and one of Nash-Williams. Finally, if G is 2-tough and s ⩾ n , then G is hamiltonian. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1016/0012-365X(90)90055-M | Discrete Mathematics |
Keywords | Field | DocType |
long cycle,large degree sum | Longest cycle,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Hamiltonian (quantum mechanics),Generalization,Cardinality,Independent set,Mathematics | Journal |
Volume | Issue | ISSN |
79 | 1 | Discrete Mathematics |
Citations | PageRank | References |
37 | 12.59 | 2 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| D. Bauer | 1 | 204 | 38.81 |
| H. J. Veldman | 2 | 262 | 44.44 |
| A. Morgana | 3 | 92 | 25.48 |
| E. F. Schmeichel | 4 | 246 | 41.69 |