图的网格可扩张性的有效识别

按照Garey和Johnson的说法,识别图的网格可嵌入性是一个很难的问题。直到现在都没有发现有效的算法。然而,这篇文章为节点的劈对的数目与阶相比充分小的图的网格可嵌入性的更有效的识别提供了一个理论根据。事实上,由本文的结果可以建立图的网格可扩张性识别和求一个图的平面嵌入的网格扩张的有效算法。     

两类图的亏格分布

一个图G的亏格分布,可用亏格多项式的形式表征.利用加边法求得两类图的亏格分布梯图(已知,但这里的求取过程较简单)与蜻蜓眼图(新的).     

关于有根3-正则平面地图的色和方程

关于色和,Tutte于1973年发表第一篇文章,是对于有根平面三角地图,即极大平面地图。于1984年,本文作者讨论了更一般的情况,即有根不可分离的平面地图。这篇文章在于提供有根3-正则平面地图色和函数所满足的方程。为此,我们先研究有根近3-正则的情况。所谓近3-正则是指至多除一个节点例外,其他节点的次皆3.这个例外的节点就是根节点。它的次为s≥2。     

有根外平面地图的节点剖分计数

一个外平面地图,即指所有节点都在同一个面边界上的平面地图。不失一般性,总可使这个面为无限面。我们先研究带限制的有根外平面地图。也就是其中无根环内部还有环的结构,而且经过相继地收缩根边所得的地图中也无这样的结构出现。     

求邻接对集的一个有效算法

图的一个邻接对集是指由其互不相交的相邻边对构成的边的子集,且去掉这些相邻边对后,所得之图是连通的．本文提供了求最大邻接对集的一个有效算法,并指出此算法可以求图的最大亏格     

哈密尔顿图的一类新的局部化充分条件

设L为图G的一个导出子图 ,若有 x ,y∈V(L) ,只要dL(x ,y) =2就有max{dG(x) ,dG(y) }≥ |G| / 2 ,则称L有局部Fan性质 .该文证明了以下结果 .G是一个 2_连通的 {K1.3 ,B1} -free图 .对任意一个整数s≥ 0 ,若G的任一个导出子图L∈ {Bi,0≤i≤s;Zs+2 }均有局部Fan性质 ,则G是Hamiltonian图 ,除非s=2且G H9.由此得到每个 2_连通的 {K1.3 ,Bi,0≤i≤s;Zs+2 }_free图除s =2且该图同构于H9外 ,均为Hamiltonian图 .     

曲面上的偏微分方程

旨在讨论三个不同形式的偏微分方程在一个整域扩张上解的存在性、唯一性以及求解使得所有系数皆正项有限和的一种方法.虽然这些方程都是在研究地图在曲面上一种同构分类时发现的,对相关的组合,或代数结构却有些普遍意义.     

二连通三正则简单图的最大亏格及结构性质

已知二连通三正则简单图的最大亏格至少为其圈秩的三分之一。且，此下界可以达到。本文表明这种达到最大亏格下界的图具有特殊结构，而且其结点数可被三整除。同时，还证明了当了点数不可被三整除时，这种图最大亏格的下界可提高一个亏格。     

图的曲面嵌入

提供了曲面的一种多边形表示，它虽然由多面形表示演化而来，但使得图的曲面嵌入的存在性、计数、确定最大亏格等问题变得十分简单．多面形表示源于Heffter^[1]．Hilbert和Cohn—Vossen提出过引线问题并将它与Heawood的地图着色猜想联系[2]．经过近百年直至Ringal等获得证明^[3，4]．Edmonds(1960)^[5]的多面形表示曾被广泛引用．但30余年后，才发现是Heffter的对偶形式．虽然多边形表示始于本文作者的专著^[6,7]，但至今才发现它在处理上述问题的效力、这就导致此文并为过渡到组合地图理论搭起一座桥梁．     

组合地图的同构

讨论组合地图的同构、识别,以及提供两个判别组合地图同构的有效算法.