کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649991 | 1342471 | 2008 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The independence number in graphs of maximum degree three
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The independence number in graphs of maximum degree three The independence number in graphs of maximum degree three](/preview/png/4649991.png)
چکیده انگلیسی
We prove that a K4K4-free graph GG of order nn, size mm and maximum degree at most three has an independent set of cardinality at least 17(4n−m−λ−tr), where λλ counts the number of components of GG whose blocks are each either isomorphic to one of four specific graphs or edges between two of these four specific graphs and tr is the maximum number of vertex-disjoint triangles in GG. Our result generalizes a bound due to Heckman and Thomas [C.C. Heckman, R. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math. 233 (2001) 233–237].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5829–5833
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5829–5833
نویسندگان
Jochen Harant, Michael A. Henning, Dieter Rautenbach, Ingo Schiermeyer,