Generating 4-connected even triangulations on the sphere

被引：4
|
作者：
Matsumoto, Naoki [1 ]
Nakamoto, Atsuhiro [1 ]
机构：
[1] Yokohama Natl Univ, Dept Math, Hodogaya Ku, Yokohama, Kanagawa 2408501, Japan
来源：
DISCRETE MATHEMATICS | 2015年 / 338卷 / 01期
关键词：
Generating theorem; 4-connected; Even triangulations; Sphere; PROJECTIVE PLANE; MINIMUM DEGREE; IRREDUCIBLE TRIANGULATIONS; CLOSED SURFACES; KLEIN BOTTLE; LEAST; QUADRANGULATIONS;
D O I：
10.1016/j.disc.2014.08.017
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this paper, we prove that every 4-connected even triangulation on the sphere can be obtained from the octahedron by a sequence of two kinds of transformations called a 4-splitting and a twin-splitting, only through 4-connected even triangulations. As a corollary, taking a dual, we can also generate all cyclically 4-edge-connected cubic bipartite graphs on the sphere. (C) 2014 Elsevier B.V. All rights resented.
引用
收藏
页码：64 / 70
页数：7
相关论文
共 50 条
  • [21] Generating Even Triangulations on the Klein Bottle
    Asayama, Yoshihiro
    Matsumoto, Naoki
    Nakamoto, Atsuhiro
    Ogano, Shota
    GRAPHS AND COMBINATORICS, 2018, 34 (04) : 727 - 757
  • [22] On 4-connected 4-regular graphs without even cycle decompositions
    Liu, Wenzhong
    Cui, Qing
    Wang, Yunzhuo
    DISCRETE MATHEMATICS, 2022, 345 (10)
  • [23] HAMILTONIAN CYCLES IN 4-CONNECTED PLANAR AND PROJECTIVE PLANAR TRIANGULATIONS WITH FEW 4-SEPARATORS
    Solomon Lo, On-Hei
    Qian, Jianguo
    SIAM Journal on Discrete Mathematics, 2022, 36 (02) : 1496 - 1501
  • [24] N-flips in even triangulations on the sphere
    Nakamoto, A
    Sakuma, T
    Suzuki, Y
    JOURNAL OF GRAPH THEORY, 2006, 51 (03) : 260 - 268
  • [25] UNCONTRACTABLE 4-CONNECTED GRAPHS
    MARTINOV, N
    JOURNAL OF GRAPH THEORY, 1982, 6 (03) : 343 - 344
  • [26] Hamiltonicity of 4-connected Graphs
    Hao LI LRI
    Acta Mathematica Sinica(English Series), 2010, 26 (04) : 699 - 710
  • [27] Hamiltonicity of 4-connected graphs
    Li, Hao
    Tian, Feng
    Xu, Zhi Xia
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2010, 26 (04) : 699 - 710
  • [28] On even triangulations of 2-connected embedded graphs
    Zhang, HM
    He, X
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2003, 2697 : 139 - 148
  • [29] On even triangulations of 2-connected embedded graphs
    Zhang, HM
    He, X
    SIAM JOURNAL ON COMPUTING, 2005, 34 (03) : 683 - 696
  • [30] Hamiltonicity of 4-connected graphs
    Hao Li
    Feng Tian
    Zhi Xia Xu
    Acta Mathematica Sinica, English Series, 2010, 26 : 699 - 710
12345