کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655519 1343388 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the number of pentagons in triangle-free graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the number of pentagons in triangle-free graphs
چکیده انگلیسی

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 Erdős in 1984.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 120, Issue 3, April 2013, Pages 722-732