کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646946 | 1342320 | 2015 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Perfect matchings avoiding prescribed edges in a star-free graph
ترجمه فارسی عنوان
سازگاری کامل با اجتناب از لبه های مجاز در گراف بدون ستاره
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تطبیق کامل، زیرگرافی ممنوع نمودارهای بدون ستاره، قابلیت انبساط
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 338, Issue 12, 6 December 2015, Pages 2260–2274
نویسندگان
Yoshimi Egawa, Jun Fujisawa, Michael D. Plummer, Akira Saito, Tomoki Yamashita,