کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418611 681695 2011 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله 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
چکیده انگلیسی

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
نویسندگان
, , ,