首页 | 本学科首页   官方微博 | 高级检索  
     


Fold‐2‐covering triangular embeddings
Authors:D. B  nard,A. Bouchet,R. B. Richter
Affiliation:D. Bénard,A. Bouchet,R. B. Richter
Abstract: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 m2 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
Keywords:triangulations  coverings  matching  flows
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号