Edge Proximity Conditions for Extendability in Planar Triangulations

被引：7
|
作者：
Fujisawa, Jun [1 ]
Ota, Katsuhiro [2 ]
机构：
[1] Keio Univ, Fac Business & Commerce, Yokohama, Kanagawa 2238521, Japan
[2] Keio Univ, Dept Math, Yokohama, Kanagawa 2238522, Japan
来源：
JOURNAL OF GRAPH THEORY | 2015年 / 80卷 / 01期
关键词：
distance restricted matching extension; triangulation; plane graph;
D O I：
10.1002/jgt.21827
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph G with at least 2m+2 vertices is said to be distance d m-extendable if for any matching M of G with m edges in which the edges lie at distance at least d pairwise, there exists a perfect matching of G containing M. In this article we prove that every 5-connected triangulation on the plane of even order is distance 3 9-extendable and distance 4 m-extendable for any m.
引用
收藏
页码：1 / 11
页数：11
相关论文
共 50 条
  • [21] EDGE INSERTION FOR OPTIMAL TRIANGULATIONS
    BERN, M
    EDELSBRUNNER, H
    EPPSTEIN, D
    MITCHELL, S
    TAN, TS
    LECTURE NOTES IN COMPUTER SCIENCE, 1992, 583 : 46 - 60
  • [22] Aircraft proximity termination conditions in the planar turn centric modes
    Huynh, Union H. -N.
    Fulton, Neale L.
    APPLIED MATHEMATICAL MODELLING, 2013, 37 (1-2) : 137 - 154
  • [23] On extendability of co-edge-regular graphs
    Kutnar, Klavdija
    Marusic, Dragan
    Miklavic, Stefko
    Sparl, Primoz
    DISCRETE APPLIED MATHEMATICS, 2021, 298 : 34 - 49
  • [24] Simultaneous edge flipping in triangulations
    Galter, J
    Hurtado, F
    Noy, M
    Pérennes, S
    Urrutia, J
    INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2003, 13 (02) : 113 - 133
  • [25] Planar triangulations, bridgeless planar maps and Tamari intervals
    Fang, Wenjie
    EUROPEAN JOURNAL OF COMBINATORICS, 2018, 70 : 75 - 91
  • [26] On random planar graphs, the number of planar graphs and their triangulations
    Osthus, D
    Prömel, HJ
    Taraz, A
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (01) : 119 - 134
  • [27] The Matching Extendability of Optimal 1-Planar Graphs
    Fujisawa, Jun
    Segawa, Keita
    Suzuki, Yusuke
    GRAPHS AND COMBINATORICS, 2018, 34 (05) : 1089 - 1099
  • [28] EDGE INSERTION FOR OPTIMAL TRIANGULATIONS
    BERN, M
    EDELSBRUNNER, H
    EPPSTEIN, D
    MITCHELL, S
    TAN, TS
    DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 10 (01) : 47 - 65
  • [29] Controllable morphing of compatible planar triangulations
    Surazhsky, V
    Gotsman, C
    ACM TRANSACTIONS ON GRAPHICS, 2001, 20 (04): : 203 - 231
  • [30] On the number of triangulations of planar point sets
    Seidel, R
    COMBINATORICA, 1998, 18 (02) : 297 - 299
12345