Informace o publikaci
On the number of pentagons in triangle-free graphs
| Autoři | |
|---|---|
| Rok publikování | 2013 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Combinatorial Theory, Series A |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.jcta.2012.12.008 |
| Klíčová slova | Pentagon density; Triangle-free graphs; Extremal graph theory |
| Popis | Using the formalism of flag algebras, we prove that every triangle-free graph G with n vertices contains at most (n/5)(5) cycles of length five. Moreover, the equality is attained only when n is divisible by five and G is the balanced blow-up of the pentagon. We also compute the maximal number of pentagons and characterize extremal graphs in the non-divisible case provided n is sufficiently large. This settles a conjecture made by Erdos in 1984. (C) 2012 Elsevier Inc. All rights reserved. |