Premium
Fold‐2‐covering triangular embeddings
Author(s) -
Bénard D.,
Bouchet A.,
Richter R. B.
Publication year - 2003
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/jgt.10070
Subject(s) - combinatorics , mathematics , conjecture , euler characteristic , vertex (graph theory) , surface (topology) , triangulation , graph , discrete mathematics , geometry
For a graph G and a positive integer m , G ( m ) is the graph obtained from G by replacing every vertex by an independent set of size m and every edge by m 2 edges joining all possible new pairs of ends. If G triangulates a surface, then it is easy to see from Euler's formula that G ( m ) can, in principle, triangulate a surface. For m prime and at least 7, it has previously been shown that in fact G ( m ) does triangulate a surface, and in fact does so as a “covering with folds” of the original triangulation. For m = 5, this would be a consequence of Tutte's 5‐Flow Conjecture. In this work, we investigate the case m = 2 and describe simple classes of triangulations G for which G (2) does have a triangulation that covers G “with folds,” as well as providing a simple infinite class of triangulations G of the sphere for which G (2) does not triangulate any surface. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 79–92, 2003