کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423570 1342419 2011 31 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The number of maximum matchings in a tree
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The number of maximum matchings in a tree
چکیده انگلیسی

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664n) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 21, 6 November 2011, Pages 2512-2542
نویسندگان
, ,