کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418611 | 681695 | 2011 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Lower bounds on the independence number of certain graphs of odd girth at least seven
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Lower bounds on the independence number of certain graphs of odd girth at least seven Lower bounds on the independence number of certain graphs of odd girth at least seven](/preview/png/418611.png)
چکیده انگلیسی
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] proved that every connected subcubic triangle-free graph GG has an independent set of order at least (4n(G)−m(G)−1)/7(4n(G)−m(G)−1)/7 where n(G)n(G) and m(G)m(G) denote the order and size of GG, respectively. We conjecture that every connected subcubic graph GG of odd girth at least seven has an independent set of order at least (5n(G)−m(G)−1)/9(5n(G)−m(G)−1)/9 and verify our conjecture under some additional technical assumptions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issues 2–3, 28 January 2011, Pages 143–151
Journal: Discrete Applied Mathematics - Volume 159, Issues 2–3, 28 January 2011, Pages 143–151
نویسندگان
Anders Sune Pedersen, Dieter Rautenbach, Friedrich Regen,