完全二部图的少面数强嵌入

通过调整完全二部图G的少双圈覆盖中的某些圈，可得到一个强嵌入，没的双圈覆盖可以得到不同的强嵌入，最后作为推论，得到完全三部图Kn,n,n可以强嵌入到某一亏格的曲面上。     

一类三正则图的嵌入亏格分布

图的嵌入亏格分布用图的嵌入多项式来表示,利用联树嵌入的方法,本文利用联树的概念,借助于刘彦佩的理论,给出了计算一类三正则图的曲面嵌入亏格分布的公式.     

一类图的亏格嵌入

在联树模型的基础上,把图在曲面上的嵌入用其联树,也即其关联曲面来表示。然后通过对关联曲面进行分类,建立递推关系式,进而得到了一类异于目前已知嵌入分布的新图类的可定向嵌入分布。     

图的曲面嵌入

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

图的曲面嵌入

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

图的曲面嵌入

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

Cm,n的最小亏格与Km,n的强嵌入

令C_m,n表示长为m的圈与n个孤立点的联结(join)所得的图. 本文证明了C_m,n的最小亏格和最小不可定向亏格与完全二部图K_m,n的相等. 同时,证明当m≥2并且n≥2时, K_m,n在其最小可定向曲面上有一个强嵌入; 当m≥3并且n≥3,时, 在最小不可定向曲面上有一个强嵌入.     

一类新图类的可定向嵌入的亏格分布

在刘彦佩提出的联树法的基础上,通过分类一类新图类的可定向嵌入曲面求出了这类图类的可定向嵌入的亏格分布.所用方法与国际上现有方法不同,且易于推广,所考虑的非平面图类比已有计算图的嵌入亏格分布文献中的非平面图更复杂.     

一类图在环面上的嵌入

图的亏格分布已被证明为NP难问题,对于大部分图类的亏格分布和完全亏格分布,暂时还没有得到.而图在不同亏格曲面上的不等价的嵌入个数往往有一定的相关关系,因此研究图在小亏格曲面上的嵌入问题对于研究图类的亏格分布也就有着重要意义.本文利用嵌入联树模型得到了由鹅卵石路图添加1条边所得到的一类图nG在环面上的嵌入个数为4n-1+(11n-29)2n-3(n≥2).     

一类特殊连通图的最大亏格的下界

主要考虑了一些特殊连通图(即含有O-型点或Ⅱ-型对点的连通图)的最大亏格的下界,得到了1/3β(G)是一些特殊连通图的最大亏格的下界。     

一类图的列表强边染色

给出了列表强边染色的定义,证明了若G为d(x)+d(y)≤5,则强边选择数Sχ′l(G)≤6.     

一类四正则图的完全亏格分布

一个图G的完全亏格多项式表征了图G的亏格(可定向,不可定向)分布情况.本文推广了Yang和Liu提出的图类,得到了一类新的四正则图,并得出了此类四正则图的完全亏格分布.     

近三角剖分图的最大亏格与1-因子

考察了平面近三角剖分图的最大亏格与独立边集之间的关系.设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2(ψ)]个独立边集,那么图G的最大亏格γM(G)≥[1/2β(G)]-1,这里(ψ)和β(G)分别表示图G在平面上嵌入的面数与G的Betti数.特别地,如果(ψ)=0 mod 2,即G有1-因子,则G是上可嵌入的.作为应用,证明了几个已知的结果.     

两类图的亏格分布

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

几类冠图的邻强边色数

图的强染色来自计算机科学,有着很强的实际背景,但确定图的强色数是非常困难的。张忠辅,刘林忠,王建方等研究了图的邻强边染色,并提出了邻强边染色猜想：对任意连通图GG,{y}≥3且G≠C5有△≤X’ax（G）≤△＋2。研究了树、圈、扇、轮、完全二部图及完全图的冠图的邻强边色数;证明了：△≤X’as（G）≤△＋1,且X’as（G）≤△＋1当且仅当G[V△]≠Ф。