論文

査読有り
2017年12月

Edge proximity and matching extension in punctured planar triangulations

DISCRETE MATHEMATICS
  • R. E. L. Aldred
  • ,
  • Jun Fujisawa
  • ,
  • Akira Saito

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

A matching M in a graph G is said to be extendable if there exists a perfect matching of G containing M. In 1989, it was shown that every connected planar graph with at least 8 vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is 5-connected.planar triangulation or 5-connected plane graphs with few non-triangular faces.
In this paper, we prove that if G is a 5-connected plane graph of even order in which at most two faces are not triangular and M is a matching of size four in which the edges lie pairwise distance at least three apart, then M is extendable. A related result concerning perfect matching with proscribed edges is shown as well. (C) 2017 Elsevier B.V. All rights reserved.

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

エクスポート
BibTeX RIS