کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650141 1342477 2009 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characterization of a class of graphs related to pairs of disjoint matchings
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Characterization of a class of graphs related to pairs of disjoint matchings
چکیده انگلیسی
For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the ratio of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that for any graph 54 is the tight upper bound for this ratio. We characterize the class of graphs for which it is precisely 54. Our characterization implies that these graphs contain a spanning subgraph, every connected component of which is the minimal graph of this class.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 4, 6 March 2009, Pages 693-713
نویسندگان
,