کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650539 1342492 2008 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the tightness of the 514 independence ratio
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the tightness of the 514 independence ratio
چکیده انگلیسی

In 1979, Staton proved that every triangle-free graph GG with maximum degree at most three has an independent set with size at least 514 of the number of vertices of GG. Fraughnaugh [size and independence in triangle-free graphs with maximum degree three, J. Graph Theory 14 (5) (1990) 525–535] and Heckman and Thomas [A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math 233 (2001) 233–237] provided shorter proofs of the same result. An analysis of the cases of equality for the main results in the last paper is presented. Also, a proof that there are only two connected triangle-free graphs with maximum degree at most three and independence ratio 514 is given; it is self-contained and does not require a computer search.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 15, 6 August 2008, Pages 3169–3179
نویسندگان
,