Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646946 | Discrete Mathematics | 2015 | 15 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yoshimi Egawa, Jun Fujisawa, Michael D. Plummer, Akira Saito, Tomoki Yamashita,