Edge proximity and matching extension in punctured planar triangulations

被引：1

作者：

Aldred, R. E. L. ^{[1
]}

Fujisawa, Jun ^{[2
]}

Saito, Akira ^{[3
]}

机构：

[1] Univ Otago, Dept Math & Stat, POB 56, Dunedin 9054, New Zealand

[2] Keio Univ, Fac Business & Commerce, Kohoku Ku, Hiyoshi 4-1-1, Yokohama, Kanagawa 2238521, Japan

[3] Nihon Univ, Dept Informat Sci, Setagaya Ku, Sakurajosui 3-25-40, Tokyo 1568550, Japan

来源：

DISCRETE MATHEMATICS | 2017年 / 340卷 / 12期

基金：

日本学术振兴会;

关键词：

Distance restricted matching extension; Punctured triangulation; Plane graph; EXTENDING MATCHINGS; GRAPHS;

D O I：

10.1016/j.disc.2017.07.017

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：2978 / 2985

页数：8

共 50 条

[21] 3-dynamic coloring of planar triangulations [J].

Asayama, Yoshihiro ;

Kawasaki, Yuki ;

Kim, Seog-Jin ;

Nakamoto, Atsuhiro ;

Ozeki, Kenta .

DISCRETE MATHEMATICS, 2018, 341 (11) :2988-2994

[22] Construction of planar 4-connected triangulations [J].

Brinkmann, Gunnar ;

Larson, Craig ;

Souffriau, Jasper ;

Van Cleemput, Nico .

ARS MATHEMATICA CONTEMPORANEA, 2015, 9 (02) :145-149

[23] Random walks on stochastic hyperbolic half planar triangulations [J].

Angel, Omer ;

Nachmias, Asaf ;

Ray, Gourab .

RANDOM STRUCTURES & ALGORITHMS, 2016, 49 (02) :213-234

[24] SAMPLING AND COUNTING 3-ORIENTATIONS OF PLANAR TRIANGULATIONS [J].

Miracle, Sarah ;

Randall, Dana ;

Streib, Amanda Pascoe ;

Tetali, Prasad .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (02) :801-831

[25] Computational Complexity of the Vertex Cover Problem in the Class of Planar Triangulations [J].

Kobylkin, K. S. .

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS, 2017, 299 :106-112

[26] Chromatic polynomials of planar triangulations, the Tutte upper bound and chromatic zeros [J].

Shrock, Robert ;

Xu, Yan .

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2012, 45 (05)

[27] Construction of acyclically 4-colourable planar triangulations with minimum degree 4 [J].

Zhu, Enqiang ;

Li, Zepeng ;

Shao, Zehui ;

Xu, Jin .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2019, 96 (09) :1723-1734

[28] Matching extension and distance spectral radius [J].

Zhang, Yuke ;

van Dam, Edwin R. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2023, 674 :244-255

[29] Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees [J].

Katoh, Naoki ;

Tanigawa, Shin-ichi .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (17) :3569-3585

[30] The structure of chromatic polynomials of planar triangulations and implications for chromatic zeros and asymptotic limiting quantities [J].

Shrock, Robert ;

Xu, Yan .

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2012, 45 (21)

← 1 2 3 4 5 →