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 条
[41]   UNAVOIDABLE SET OF CONFIGURATIONS IN PLANAR TRIANGULATIONS [J].
APPEL, K ;
HAKEN, W .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 26 (01) :1-21
[42]   Counting Hamiltonian cycles in planar triangulations [J].
Liu, Xiaonan ;
Wang, Zhiyu ;
Yu, Xingxing .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2022, 155 :256-277
[43]   INDEPENDENT DOMINATING SETS IN PLANAR TRIANGULATIONS [J].
Botler, Fabio ;
Fernandes, Cristina G. ;
Gutierrez, Juan .
PROCEEDINGS OF THE 12TH EUROPEAN CONFERENCE ON COMBINATORICS, GRAPH THEORY AND APPLICATIONS, EUROCOMB 2023, 2023, :163-168
[44]   A theorem on paths in locally planar triangulations [J].
Kawarabayashi, K .
EUROPEAN JOURNAL OF COMBINATORICS, 2004, 25 (06) :781-784
[45]   On the oriented diameter of near planar triangulations [J].
Ge, Yiwei ;
Liu, Xiaonan ;
Wang, Zhiyu .
DISCRETE MATHEMATICS, 2025, 348 (05)
[46]   Independent Domination Number of Planar Triangulations [J].
Francis, P. ;
Illickan, Abraham M. ;
Jose, Lijo M. ;
Rajendraprasad, Deepak .
JOURNAL OF GRAPH THEORY, 2025,
[47]   Morphing Schnyder drawings of planar triangulations [J].
Barrera-Cruz, Fidel ;
Haxell, Penny ;
Lubiw, Anna .
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8871 :294-305
[48]   Morphing Schnyder Drawings of Planar Triangulations [J].
Barrera-Cruz, Fidel ;
Haxell, Penny ;
Lubiw, Anna .
GRAPH DRAWING (GD 2014), 2014, 8871 :294-305
[49]   NUMBER OF HAMILTONIAN CYCLES IN PLANAR TRIANGULATIONS [J].
Liu, Xiaonan ;
Yu, Xingxing .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) :1005-1021
[50]   Independent Dominating Sets in Planar Triangulations [J].
Botler, Fabio ;
Fernandes, Cristina G. ;
Gutierrez, Juan .
ELECTRONIC JOURNAL OF COMBINATORICS, 2024, 31 (02)