کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656996 1343706 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Longest cycles in k-connected graphs with given independence number
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Longest cycles in k-connected graphs with given independence number
چکیده انگلیسی

The Chvátal–Erdős Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In 1976, Fouquet and Jolivet conjectured an extension: If G is an n-vertex k-connected graph with independence number a, and a⩾k, then G has a cycle with length at least . We prove this conjecture.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 101, Issue 6, November 2011, Pages 480-485