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 条
  • [41] Morphing Schnyder drawings of planar triangulations
    University of Waterloo, Waterloo, Canada
    Lect. Notes Comput. Sci., (294-305):
  • [42] A theorem on paths in locally planar triangulations
    Kawarabayashi, K
    EUROPEAN JOURNAL OF COMBINATORICS, 2004, 25 (06) : 781 - 784
  • [43] Morphing Schnyder Drawings of Planar Triangulations
    Barrera-Cruz, Fidel
    Haxell, Penny
    Lubiw, Anna
    GRAPH DRAWING (GD 2014), 2014, 8871 : 294 - 305
  • [44] Distance matching in punctured planar triangulations
    Aldred, R. E. L.
    Plummer, Michael D.
    JOURNAL OF COMBINATORICS, 2016, 7 (2-3) : 509 - 530
  • [45] NUMBER OF HAMILTONIAN CYCLES IN PLANAR TRIANGULATIONS
    Liu, Xiaonan
    Yu, Xingxing
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) : 1005 - 1021
  • [46] Independent Dominating Sets in Planar Triangulations
    Botler, Fabio
    Fernandes, Cristina G.
    Gutierrez, Juan
    ELECTRONIC JOURNAL OF COMBINATORICS, 2024, 31 (02):
  • [47] Diagonal flips in labelled planar triangulations
    Gao, ZC
    Urrutia, J
    Wang, JY
    GRAPHS AND COMBINATORICS, 2001, 17 (04) : 647 - 657
  • [48] Minimum balanced bipartitions of planar triangulations
    Shantanam, Abhinav
    DISCRETE MATHEMATICS, 2020, 343 (0I)
  • [49] The number of triangulations on planar point sets
    Welzl, Emo
    GRAPH DRAWING, 2007, 4372 : 1 - 4
  • [50] Rooted HIST property on planar triangulations
    Tsuchiya, Shoichi
    ARS COMBINATORIA, 2016, 126 : 29 - 40
12345