論文

査読有り 責任著者
2015年12月

Perfect matchings avoiding prescribed edges in a star-free graph

DISCRETE MATHEMATICS
  • Yoshimi Egawa
  • ,
  • Jun Fujisawa
  • ,
  • Michael D. Plummer
  • ,
  • Akira Saito
  • ,
  • Tomoki Yamashita

338
12
開始ページ
2260
終了ページ
2274
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1016/j.disc.2015.05.014
出版者・発行元
ELSEVIER SCIENCE BV

Aldred and Plummer (1999) have proved that every m-connected K-1,K-m-k+2-free graph of even order contains a perfect matching which avoids k prescribed edges. They have also proved that the result is best possible in the range 1 <= k <= 1/2(m + 1). In this paper, we show that if 1/2(m + 2) <= k <= m - 1, their result is not best possible. We prove that if m >= 4 and 1/2(m + 2) <= k <= m - 1, every K-1,K-[2m-k+4/3]-free graph of even order contains a perfect matching which avoids k prescribed edges. While this is a best possible result in terms of the order of a forbidden star, if 2m - k + 4 equivalent to 0 (mod 3), we also prove that only finitely many sharpness examples exist. (C) 2015 Elsevier B.V. All rights reserved.

リンク情報
DOI
https://doi.org/10.1016/j.disc.2015.05.014
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000359955700012&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.disc.2015.05.014
  • ISSN : 0012-365X
  • eISSN : 1872-681X
  • Web of Science ID : WOS:000359955700012

エクスポート
BibTeX RIS