Distance matching in punctured planar triangulations

被引:5
|
作者
Aldred, R. E. L. [1 ]
Plummer, Michael D. [2 ]
机构
[1] Univ Otago, Dept Math & Stat, POB 56, Dunedin 9054, New Zealand
[2] Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA
关键词
D O I
10.4310/JOC.2016.v7.n2.a15
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Distance matching extension with prescribed and proscribed edges in planar triangulations has been previously studied. In the present work, matching extension behavior is investigated when the graph families are slightly more general than triangulations. More particularly, we replace the triangulation hypothesis with the weaker hypotheses that (a) the graph is locally connected and (b) the graph has at most two non-triangular faces. We investigate which distance matching properties enjoyed by triangulations are retained and which are lost.
引用
收藏
页码:509 / 530
页数:22
相关论文
共 50 条
  • [1] Edge proximity and matching extension in punctured planar triangulations
    Aldred, R. E. L.
    Fujisawa, Jun
    Saito, Akira
    DISCRETE MATHEMATICS, 2017, 340 (12) : 2978 - 2985
  • [2] Distance-restricted matching extension in planar triangulations
    Aldred, R. E. L.
    Plummer, Michael D.
    DISCRETE MATHEMATICS, 2010, 310 (20) : 2618 - 2636
  • [3] Asymmetric distance matching extension in 5-connected even planar triangulations
    Aldred, R. E. L.
    Plummer, Michael D.
    Ruksasakchai, Watcharintorn
    AUSTRALASIAN JOURNAL OF COMBINATORICS, 2021, 79 : 1 - 14
  • [4] Proximity Thresholds for Matching Extension in Planar and Projective Planar Triangulations
    Aldred, R. E. L.
    Plummer, Michael D.
    JOURNAL OF GRAPH THEORY, 2011, 67 (01) : 38 - 46
  • [5] Distance-restricted matching extension in triangulations of the torus and the Klein bottle
    Aldred, R. E. L.
    Fujisawa, Jun
    ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (03):
  • [6] IRREDUCIBLE TRIANGULATIONS OF THE ONCE-PUNCTURED TORUS
    Lawrencenko, S.
    Sulanke, T.
    Villar, M. T.
    Zgonnik, L. V.
    Chavez, M. J.
    Portillo, J. R.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2018, 15 : 277 - 304
  • [7] Restricted matching in plane triangulations and near triangulations
    Aldred, R. E. L.
    Plummer, Michael D.
    Ruksasakchai, Watcharintorn
    DISCRETE APPLIED MATHEMATICS, 2020, 284 : 251 - 261
  • [8] Generating punctured surface triangulations with degree at least 4
    Chavez, Maria-Jose
    Negami, Seiya
    Quintero, Antonio
    Villar-Linan, Maria Trinidad
    ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA, 2022, 30 (01): : 129 - 151
  • [9] Flip distance between triangulations of a planar point set is APX-hard
    Pilz, Alexander
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2014, 47 (05): : 589 - 604
  • [10] A CENSUS OF PLANAR TRIANGULATIONS
    TUTTE, WT
    CANADIAN JOURNAL OF MATHEMATICS, 1962, 14 (01): : 21 - &