Article ID Journal Published Year Pages File Type
4646946 Discrete Mathematics 2015 15 Pages PDF
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
, , , , ,