### Abstract

Original language | Undefined |
---|---|

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
- IR-71423
- pancyclic
- sum
- tough
- METIS-140776
- Hamiltonian

### Cite this

*Journal of graph theory*,

*25*(4), 253-256. https://doi.org/10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J

}

*Journal of graph theory*, vol. 25, no. 4, pp. 253-256. https://doi.org/10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J

**Degree sums for edges and cycle lengths in graphs.** / Brandt, Stephan; Veldman, H.J.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Degree sums for edges and cycle lengths in graphs

AU - Brandt, Stephan

AU - Veldman, H.J.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - Circumference

KW - Closure

KW - Cycle

KW - Graph

KW - Degree

KW - IR-71423

KW - pancyclic

KW - sum

KW - tough

KW - METIS-140776

KW - Hamiltonian

U2 - 10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J

DO - 10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J

M3 - Article

VL - 25

SP - 253

EP - 256

JO - Journal of graph theory

JF - Journal of graph theory

SN - 0364-9024

IS - 4

ER -