Premium
Generating quadrangulations of surfaces with minimum degree at least 3
Author(s) -
Nakamoto Atsuhiro
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199903)30:3<223::aid-jgt7>3.0.co;2-m
Subject(s) - mathematics , dual polyhedron , combinatorics , degree (music) , vertex (graph theory) , graph , sequence (biology) , discrete mathematics , physics , acoustics , biology , genetics
In this article, we show that all quadrangulations of the sphere with minimum degree at least 3 can be constructed from the pseudo‐double wheels, preserving the minimum degree at least 3, by a sequence of two kinds of transformations called “vertex‐splitting” and “4‐cycle addition.” We also consider such generating theorems for other closed surfaces. These theorems can be translated into those of 4‐regular graphs on surfaces by taking duals. © 1999 John Wiley & Sons, In. J Graph Theory 30: 223–234, 1999