کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420827 683987 2006 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Well-covered graphs and factors
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Well-covered graphs and factors
چکیده انگلیسی

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality αα. Plummer [Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91–98] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G   without isolated vertices has a perfect [1,2][1,2]-factor FGFG, i.e. a spanning subgraph such that each component is 1-regular or 2-regular. Here, we characterize all well-covered graphs G   satisfying α(G)=α(FG)α(G)=α(FG) for some perfect [1,2][1,2]-factor FGFG. This class contains all well-covered graphs G without isolated vertices of order n   with α⩾(n-1)/2α⩾(n-1)/2, and in particular all very well-covered graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 9, 1 June 2006, Pages 1416–1428
نویسندگان
, ,