稠密图的三角剖分嵌入(英文)  

Triangular Embeddings of Dense Graphs

作　　者：任韩[1] 镡松龄 马登举[3] 

机构地区：[1]华东师范大学数学系,上海200062 [2]乔治亚州立大学数理统计系 [3]南通大学理学院计算科学与统计学系,江苏南通226019

出　　处：《昆明理工大学学报（自然科学版）》2012年第2期83-87,共5页Journal of Kunming University of Science and Technology(Natural Science)

基　　金：Supported by the National Natural Science Foundation of China(Granted No.10271048,10671073);Supported by Science and Technology Commission of Shanghai Municipality(Granted No.07XD14011

摘　　要：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-面染色的).G.Ringel posed the problem to find a sufficient and necessary condition for a graph to triangulate an orientable surface.B.Mohar and C.Thomassen raised the following problem: Does there exist a number c:0<c<1,such that every graph with n vertices,whose minimal degree is at least cn and whose number of edges is divisible by 3,which triangulates an orientable surface? Here,in this paper we show that such number c does not exist,that is,for any number c:0<c<1,there are infitely many graphs of order n,with δG)≥cn,and |E(G)|≡0(mod 3) which can't triangulate any orientable surface.Furthermore,we investigate the Hamiltonian embeddings of Kn,n and show that Kn,n has at least((n-1)!)2 distinct embeddings in Sg,(g=n-1 2)),which implies that Kn,n,n has at least n!((n-1)!)2 distinct two-face colorable triangular embeddings in the same surface.

关 键 词：三角剖分嵌入 Hamilton-嵌入 亏格嵌入 

分 类 号：O157.5[理学—数学]