All tight descriptions of 3-paths in plane graphs with girth at least 7

被引:1
作者
Borodin, O. V. [1 ]
Ivanova, A. O. [2 ]
机构
[1] Sobolev Inst Math, Novosibirsk 630090, Russia
[2] Ammosov North Eastern Fed Univ, Yakutsk 677013, Russia
关键词
Plane graph; Structure properties; Tight description; 3-path; Weight; Girth;
D O I
10.1016/j.disc.2021.112335
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Lebesgue (1940) proved that every plane graph with minimum degree delta at least 3 and girth g (the length of a shortest cycle) at least 5 has a path on three vertices (3-path) of degree 3 each. A description of 3-paths is tight if none of its parameter can be strengthened, and no triplet dropped. Borodin et al. (2013) gave a tight description of 3-paths in plane graphs with delta >= 3 and g >= 3, and another tight description was given by Borodin, Ivanova and Kostochka in 2017. In 2015, we gave seven tight descriptions of 3-paths when delta >= 3 and g >= 4. Furthermore, we proved that this set of tight descriptions is complete, which was a result of a new type in the structural theory of plane graphs. Also, we characterized (2018) all one-term tight descriptions if delta >= 3 and g >= 3. The problem of producing all tight descriptions for g >= 3 remains widely open even for delta >= 3. Eleven tight descriptions of 3-paths were obtained for plane graphs with delta = 2 and g >= 4 by Jendrol', Macekova, Montassier, and Sotak, four of which are descriptions for g >= 9. In 2018, Aksenov, Borodin and Ivanova proved nine new tight descriptions of 3-paths for delta = 2 and g >= 9 and showed that no other tight descriptions exist. Recently, we resolved the case g >= 8. The purpose of this paper is to give a complete list of 15 tight descriptions of 3-paths in the plane graphs with delta = 2 and g >= 7. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数:9
相关论文
共 28 条
  • [1] Aksenov VA, 2015, ELECTRON J COMB, V22
  • [2] ALL TIGHT DESCRIPTIONS OF 3-PATHS IN PLANE GRAPHS WITH GIRTH AT LEAST 9
    Aksenov, Valerii Anatol'evich
    Borodin, Oleg Veniaminovich
    Ivanova, Anna Olegovna
    [J]. SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2018, 15 : 1174 - 1181
  • [3] Ando K., 1993, ANN M MATH SOC JAP
  • [4] All Tight Descriptions of 4-Paths in 3-Polytopes with Minimum Degree 5
    Batueva, Ts. Ch. -D.
    Borodin, O. V.
    Ivanova, A. O.
    [J]. GRAPHS AND COMBINATORICS, 2017, 33 (01) : 53 - 62
  • [5] JOINT EXTENSION OF 2 THEOREMS OF KOTZIG ON 3-POLYTOPES
    BORODIN, O
    [J]. COMBINATORICA, 1993, 13 (01) : 121 - 125
  • [6] ALL TIGHT DESCRIPTIONS OF 3-PATHS IN PLANE GRAPHS WITH GIRTH AT LEAST 8
    Borodin, O., V
    Ivanova, A. O.
    [J]. SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2020, 17 : 496 - 501
  • [7] Borodin OV, 2019, SIB ELECTRON MATH RE, V16, P1334
  • [8] All one-term tight descriptions of 3-paths in normal plane maps without K4 - e
    Borodin, O., V
    Ivanova, A. O.
    [J]. DISCRETE MATHEMATICS, 2018, 341 (12) : 3425 - 3433
  • [9] Tight Descriptions of 3-Paths in Normal Plane Maps: Dedicated to Andre Raspaud on the occasion of his 70th birthday.
    Borodin, O. V.
    Ivanova, A. O.
    Kostochka, A. V.
    [J]. JOURNAL OF GRAPH THEORY, 2017, 85 (01) : 115 - 132
  • [10] Describing 4-paths in 3-polytopes with minimum degree 5
    Borodin, O. V.
    Ivanova, A. O.
    [J]. SIBERIAN MATHEMATICAL JOURNAL, 2016, 57 (05) : 764 - 768