稠密图的三角剖分嵌入(英文)
来源期刊：昆明理工大学学报(自然科学版)2012年第2期
论文作者：任韩 镡松龄 马登举
文章页码：83 - 87
关键词：三角剖分嵌入;Hamilton-嵌入;亏格嵌入;
摘 要：Ringel提出寻找一个图可以三角剖分给定可定向曲面的充分必要条件.针对这一问题,Mo-har和Thomassen在他们的专著《曲面上的嵌入图》中进一步提出下列公开问题:是否存在常数c:0<c<1,使得每一个n阶简单图G,如果它的每一个节点的度数至少是cn,而且它的边数可以被3整除,那么G就可以三角剖分一个可定向曲面?本文证明了这样的常数是不存在的,即对于任意常数c:0<c<1,有无限多个反例,它们的最小度大于等于cn,同时边数是3的倍数,却不可能三角剖分任何一个可定向曲面.另外,我们研究了完全二部图Kn,n的Hamilton嵌入性质,证明Kn,n在Sg（g=（n-1 2））上至少有（（n-1）!）2个Hamilton嵌入.这个结果表明完全三部图Kn,n,n在Sg（g=（n-1 2））上至少有n!（（n-1）!）2个不同的三角剖分嵌入（它们是可2-面染色的）.
任韩1，镡松龄2，马登举3
1. 华东师范大学数学系2. 乔治亚州立大学数理统计系3. 南通大学理学院计算科学与统计学系
摘 要：Ringel提出寻找一个图可以三角剖分给定可定向曲面的充分必要条件.针对这一问题,Mo-har和Thomassen在他们的专著《曲面上的嵌入图》中进一步提出下列公开问题:是否存在常数c:0<c<1,使得每一个n阶简单图G,如果它的每一个节点的度数至少是cn,而且它的边数可以被3整除,那么G就可以三角剖分一个可定向曲面?本文证明了这样的常数是不存在的,即对于任意常数c:0<c<1,有无限多个反例,它们的最小度大于等于cn,同时边数是3的倍数,却不可能三角剖分任何一个可定向曲面.另外,我们研究了完全二部图Kn,n的Hamilton嵌入性质,证明Kn,n在Sg（g=（n-1 2））上至少有（（n-1）!）2个Hamilton嵌入.这个结果表明完全三部图Kn,n,n在Sg（g=（n-1 2））上至少有n!（（n-1）!）2个不同的三角剖分嵌入（它们是可2-面染色的）.
关键词：三角剖分嵌入;Hamilton-嵌入;亏格嵌入;
