Abstract
Let G be a graph of order n satisfying d(u) + d(v) n for every edge uv of G. We show that the circumference - the length of a longest cycle - of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length between 3 and the circumference, unless G is complete bipartite. If G is 1-tough then it is pancyclic or G = Kr,r with r = n/2.
Original language | English |
---|---|
Pages (from-to) | 253-256 |
Number of pages | 4 |
Journal | Journal of graph theory |
Volume | 25 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1997 |
Keywords
- Circumference
- Closure
- Cycle
- Graph
- Degree
- Pancyclic
- Sum
- Tough
- Hamiltonian