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 条

[11] Generating weakly 4-connected matroids
Geelen, Jim
Zhou, Xiangqian
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (03) : 538 - 557
[12] LARGEST 4-CONNECTED COMPONENTS OF 3-CONNECTED PLANAR TRIANGULATIONS
BENDER, EA
RICHMOND, LB
WORMALD, NC
RANDOM STRUCTURES & ALGORITHMS, 1995, 7 (04) : 273 - 285
[13] The (3,1)-ordering for 4-connected planar triangulations
Biedl T.
Derka M.
J. Graph Algorithms and Appl., 2 (347-362): : 347 - 362
[14] On 4-connected graphs without even cycle decompositions
Rizzi, R
DISCRETE MATHEMATICS, 2001, 234 (1-3) : 181 - 186
[15] Hamiltonian cycles in 4-connected plane triangulations with few 4-separators
Lo, On-Hei Solomon
DISCRETE MATHEMATICS, 2020, 343 (12)
[16] Generating even triangulations on the torus
Matsumoto, Naoki
Nakamoto, Atsuhiro
Yamaguchi, Tsubasa
DISCRETE MATHEMATICS, 2018, 341 (07) : 2035 - 2048
[17] Decomposing 4-connected planar triangulations into two trees and one path
Knauer, Kolja
Ueckerdt, Torsten
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 134 : 88 - 109
[18] Generating an internally 4-connected binary matroid from another
Zhou, Xiangqian
DISCRETE MATHEMATICS, 2012, 312 (15) : 2375 - 2387
[19] Generating even triangulations of the projective plane
Suzuki, Yusuke
Watanabe, Takahiro
JOURNAL OF GRAPH THEORY, 2007, 56 (04) : 333 - 349
[20] Generating Even Triangulations on the Klein Bottle
Yoshihiro Asayama
Naoki Matsumoto
Atsuhiro Nakamoto
Shota Ogano
Graphs and Combinatorics, 2018, 34 : 727 - 757

← 1 2 3 4 5 →