On the distribution of cycle lengths in graphs

A. Gyárfás, J. Komlós, E. Szemerédi

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


The set of different cycle lengths of a graph G is denoted by C(G). We study how the distribution of C(G) depends on the minimum degree of G. We prove two results indicating that C(G) is dense in some sense. These results lead to the solution of a conjecture of Erdös and Hajnal stating that for suitable positive constants a, b the following holds: (Formula Presented.) where δ(G) denotes the minimum degree of G.

Original languageEnglish (US)
Pages (from-to)441-462
Number of pages22
JournalJournal of Graph Theory
Issue number4
StatePublished - 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


Dive into the research topics of 'On the distribution of cycle lengths in graphs'. Together they form a unique fingerprint.

Cite this