کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646946 1342320 2015 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Perfect matchings avoiding prescribed edges in a star-free graph
ترجمه فارسی عنوان
سازگاری کامل با اجتناب از لبه های مجاز در گراف بدون ستاره
کلمات کلیدی
تطبیق کامل، زیرگرافی ممنوع نمودارهای بدون ستاره، قابلیت انبساط
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Aldred and Plummer (1999) have proved that every mm-connected K1,m−k+2K1,m−k+2-free graph of even order contains a perfect matching which avoids kk prescribed edges. They have also proved that the result is best possible in the range 1≤k≤12(m+1). In this paper, we show that if 12(m+2)≤k≤m−1, their result is not best possible. We prove that if m≥4m≥4 and 12(m+2)≤k≤m−1, every K1,⌈2m−k+43⌉-free graph of even order contains a perfect matching which avoids kk prescribed edges. While this is a best possible result in terms of the order of a forbidden star, if 2m−k+4≡0(mod3), we also prove that only finitely many sharpness examples exist.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 12, 6 December 2015, Pages 2260–2274
نویسندگان
, , , , ,