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

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在球面S0(或环面S1)上有近-三角剖分嵌入,那么G在每一个可定向曲面Sk有近-三角剖分嵌入,其中k=h,h+1,…)[β(G)/2], 而h=0(或1)并且β(G)是图G的Betti数．特别地,G是上可嵌入的．

完全图K_(19)在可定向曲面的三角剖分嵌入数

首先由完全图K_(19)的两种电流图满足KCL电流定律,建立线性方程组,利用计算机求出方程组的所有解,由一组解对应K_(19)电流图的一种电流赋值方式,得到两种电流图的不同电流赋值方式数为34和6,然后求出K_(19)两种电流图的基础图在可定向曲面上分别有16种不同的单面嵌入;由上面的结论得到完全图K_(19)在可定向曲面上至少有640种不同的三角剖分嵌入.最后在两种电流图中求出不强同构的个数,且任意一个电流图无非平凡强自同构,从而可得K_(19)在可定向曲面上有24个不同构的三角剖分嵌入.

An Interpolation Theorem for Near-Triangulations

A near-triangular embedding is an embedded graph into some surface whose all but one facial walks are 3-gons. In this paper we show that if a graph G is a triangulation of an orientable surface Sh, then G has a near-triangular embedding into Sk for k=h, h＋1,...1,[β（G）/2], where β（G） is the Betti number of G.