کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649988 1342471 2008 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The intersection of all maximum stable sets of a tree and its pendant vertices
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The intersection of all maximum stable sets of a tree and its pendant vertices
چکیده انگلیسی

A stable   set in a graph GG is a set of mutually non-adjacent vertices, α(G)α(G) is the size of a maximum stable set of GG, and core(G) is the intersection of all its maximum stable sets. It is known that if GG is a connected graph of order n≥2n≥2 with 2α(G)>n2α(G)>n, then |core(G)|≥2, [V.E. Levit, E. Mandrescu, Combinatorial properties of the family of maximum stable sets of a graph, Discrete Applied Mathematics 117 (2002) 149–161; E. Boros, M.C. Golumbic, V.E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Applied Mathematics 124 (2002) 17–25]. When we restrict ourselves to the class of trees, we add some structural properties to this statement. Our main finding is the theorem claiming that if TT is a tree of order n≥2n≥2, with 2α(T)>n2α(T)>n, then at least two pendant vertices an even distance apart belong to core(T).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5809–5814
نویسندگان
, ,