Name
Abstract | ||
|---|---|---|
Let G be a 2-connected graph of order n , r a real number and V r = v ϵ V ( G )¦ d ( v )⩾ r . It is shown that G contains a cycle missing at most max {0, n − 2 r } vertices of V r , yielding a common generalization of a result of Dirac and one of Shi Ronghua. A stronger conclusion holds if r ⩾ 1 3 ( n +2): G contains a cycle C such that either V ( C )⊇ V r or ¦ V ( C )¦⩾2 r . This theorem extends a result of Häggkvist and Jackson and is proved by first showing that if r ⩾ 1 3 ( n +2), then G contains a cycle C for which ¦ V r ∩ V ( C )¦is maximal such that N ( x )⊆ V ( C ) whenever x ϵ V r − V ( C ) (∗). A result closely related to (∗) is stated and a result of Nash-Williams is extended using (∗). |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0012-365X(92)90612-J | Discrete Mathematics |
Keywords | Field | DocType |
large degree,discrete mathematics | Existence theorem,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Hamiltonian path,Cycle graph,Dirac (video compression format),Real number,Mathematics | Journal |
Volume | Issue | ISSN |
101 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
5 | 0.85 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. J. Veldman | 1 | 262 | 44.44 |