首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Edge proximity and matching extension in punctured planar triangulations
Authors:REL Aldred  Jun Fujisawa  Akira Saito
Institution:1. Department of Mathematics and Statistics, University of Otago, P.O. Box 56, Dunedin 9054, New Zealand;2. Faculty of Business and Commerce, Keio University, Hiyoshi 4-1-1, Kohoku-Ku, Yokohama, Kanagawa 223-8521, Japan;3. Department of Information Science, Nihon University, Sakurajosui 3-25-40, Setagaya-Ku, Tokyo 156-8550, Japan
Abstract: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.
Keywords:Distance restricted matching extension  Punctured triangulation  Plane graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号