Fold‐2‐covering triangular embeddings

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