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
}
Degree sums for edges and cycle lengths in graphs. / Brandt, Stephan; Veldman, H.J.
In: Journal of graph theory, Vol. 25, No. 4, 1997, p. 253-256.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 -