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

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

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

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

一类图的亏格嵌入

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

两类重复边合并图的亏格

把图G的某条边和图H的某条边合并在一起构成的图,记作G*eH,在刘彦佩提出联树的基础上,通过把关联曲面逐层分段,得到了n个K5(K3,3)的边合并图K5*eK5*e…*eK5(K3.3*eK3.3*e…*eK3.3)的亏格为「n/2].     

两类图的亏格分布

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

一类图在环面上的嵌入

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

联树模型在亏格等式证明中的应用

应用联树模型,把图浸入平面,获得这个图的关联曲面,从而获得这个图的嵌入曲面的亏格.应用这个方法,我们证明了2个著名的亏格等式.第1如果e是图G的一条割边,G-e有2个分支G1,G2,那么,g(G1) g(G2)=g(G).其中g(G)表示图G的亏格.第2用H*vK表示图H与K在点v处的结合,即V(H)∩V(K)=v,E(H)∩E(K)=φ.γ(G)表示图G的最小可定向亏格.那么,γ(H*vK)=γ(H) γ(K).     

类树图亏格分布的单峰性

图的亏格分布是否为单峰,这一猜想至今没有得到证明.文章首先给出了单峰性的概念及性质,并进一步推导得到了单峰性的另一重要性质。在此基础上,使用分类讨论的方法,证明了类树图的亏格分布是单峰的.     

类树图的亏格多项式问题

一个图G的亏格多项式表征了图G亏格的亏格分布情况.本文在解决M系列图的亏格多项式的基础上,利用切分与还原的方法,建立了计算类树图的亏格多项式的公式.     

图的曲面嵌入

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

3-正则图的最大亏格计算公式

本文主要讨论了三正则连通图的叶子数l(T)以及叶子数与图的最大亏格γM之间的关系,并给出了3-正则图的最大亏格的计算公式:γM=12(l(T) pα-pβ);这里,T是图G的XUONG树,l(T)是T的叶子数;pα,pβ分别是G-T的偶长路数和奇长圈数.作为应用我们计算了若干类图的最大亏格.     

一类由圈长分布确定的图

阶为ｎ的图Ｇ的圈长分布是序列（ｃ１，ｃ２，…，ｃｎ），其中ｃｉ是Ｇ中长为ｉ的圈的数目．本文证明了下述结果：设Ａ　Ｅ（Ｋｎ），｜Ａ｜３，ｎ≥｜Ａ｜十３，，则Ｋｎ—Ａ是由它的圈长分布确定的．     

关于图的全染色和列表全染色方面的一些结果

证明了如下结果：一个简单连通图G的全色数和列表全色数都为△＋1，如果它存在一个支撑子树T使得△（G）≥6和△（G\E（T））≤2，或者△（G）≥4和△（G\E（T））≤1。     

一类图的强最大亏格嵌入

图的嵌入理论是拓扑图论中一个中心课题.图的最大亏格嵌入的刻画和研究已较完善.但对于强嵌入,这方面的讨论却很少.本文对于平面上的不含不交(指无公共节点)圈的图以及完全图K5,利用构造强最大亏格嵌入的方法,给出了强最大亏格.同时,也给出了完全二部图K3,k(k≥3)的不可定向强最大亏格的一个下界.     

关于一类新的上可嵌入图的研究

讨论了由直径为3的无环图构造出的一类特殊图的上可嵌入性.通过给直径为3的重图加边,提供了一类新的上可嵌入图;进而给出了直径为2的无环图是上可嵌入的另一种证明.     

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

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