کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657142 1343719 2009 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Matchings in regular graphs from eigenvalues
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Matchings in regular graphs from eigenvalues
چکیده انگلیسی

Let G be a connected k-regular graph of order n. We find a best upper bound (in terms of k) on the third largest eigenvalue that is sufficient to guarantee that G has a perfect matching when n is even, and a matching of order n−1 when n is odd. We also examine how other eigenvalues affect the size of matchings in G.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 99, Issue 2, March 2009, Pages 287-297