کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777607 | 1632967 | 2017 | 38 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximising the number of induced cycles in a graph
ترجمه فارسی عنوان
حداکثر تعداد چرخه های القا شده در یک گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
زیرگرافهای منجر شده، سوراخ، قابل انعطاف،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We determine the maximum number of induced cycles that can be contained in a graph on nâ¥n0 vertices, and show that there is a unique graph that achieves this maximum. This answers a question of Chvátal and Tuza from the 1980s. We also determine the maximum number of odd or even induced cycles that can be contained in a graph on nâ¥n0 vertices and characterise the extremal graphs. This resolves a conjecture of Chvátal and Tuza from 1988.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 126, September 2017, Pages 24-61
Journal: Journal of Combinatorial Theory, Series B - Volume 126, September 2017, Pages 24-61
نویسندگان
Natasha Morrison, Alex Scott,