کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903910 | 1632965 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The maximum number of cliques in graphs without long cycles
ترجمه فارسی عنوان
حداکثر تعداد کلاکی ها در نمودارها بدون چرخه طولانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The ErdÅs-Gallai Theorem states that for kâ¥3 every graph on n vertices with more than 12(kâ1)(nâ1) edges contains a cycle of length at least k. Kopylov proved a strengthening of this result for 2-connected graphs with extremal examples Hn,k,t and Hn,k,2. In this note, we generalize the result of Kopylov to bound the number of s-cliques in a graph with circumference less than k. Furthermore, we show that the same extremal examples that maximize the number of edges also maximize the number of cliques of any fixed size. Finally, we obtain the extremal number of s-cliques in a graph with no path on k-vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 128, January 2018, Pages 219-226
Journal: Journal of Combinatorial Theory, Series B - Volume 128, January 2018, Pages 219-226
نویسندگان
Ruth Luo,