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
关键词
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 条
  • [1] Edge proximity conditions for extendability in regular bipartite graphs
    Aldred, R. E. L.
    Jackson, Bill
    Plummer, Michael D.
    JOURNAL OF GRAPH THEORY, 2023, 104 (02) : 282 - 288
  • [2] Edge proximity conditions for extendability in cubic bipartite graphs
    Aldred, R. E. L.
    Jackson, Bill
    JOURNAL OF GRAPH THEORY, 2007, 55 (02) : 112 - 120
  • [3] Edge proximity and matching extension in punctured planar triangulations
    Aldred, R. E. L.
    Fujisawa, Jun
    Saito, Akira
    DISCRETE MATHEMATICS, 2017, 340 (12) : 2978 - 2985
  • [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] Dyck path triangulations and extendability
    Ceballos, Cesar
    Padrol, Arnau
    Sarmiento, Camilo
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2015, 131 : 187 - 208
  • [6] Proximity in triangulations and quadrangulations
    Czabarka, Eva
    Dankelmann, Peter
    Olsen, Trevor
    Szekely, Laszlo
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2022, 10 (02) : 425 - 446
  • [7] Edge proximity and matching extension in projective planar graphs
    Fujisawa, Jun
    Seno, Hiroki
    JOURNAL OF GRAPH THEORY, 2020, 95 (03) : 341 - 367
  • [8] A CENSUS OF PLANAR TRIANGULATIONS
    TUTTE, WT
    CANADIAN JOURNAL OF MATHEMATICS, 1962, 14 (01): : 21 - &
  • [9] An Isoperimetric Inequality for Planar Triangulations
    Angel, Omer
    Benjamini, Itai
    Horesh, Nizan
    DISCRETE & COMPUTATIONAL GEOMETRY, 2018, 59 (04) : 802 - 809
  • [10] Planar stochastic hyperbolic triangulations
    Curien, Nicolas
    PROBABILITY THEORY AND RELATED FIELDS, 2016, 165 (3-4) : 509 - 540