论文部分内容阅读
图在曲面上的嵌入起源于地图着色定理的证明.这里,曲面S就是无边缘的紧2-维闭流形,分为可定向曲面与不可定向曲面.连通图G在曲面S上的2-胞腔嵌入,简称为嵌入,是指存在一个1—1连续映射φ:G→S使得S-φ(G)的每个连通分支都同胚于一个开圆盘.图G的最小亏格,γ(G),就是最小的整数n使得图G能嵌入到亏格为n的可定向曲面Sn.图G的最大亏格,γM(G),就是最大的整数n使得图G能嵌入到亏格为n的可定向曲面Sn.1966年,Duke[12]得到了可定向曲面嵌入的插值定理:若图G可嵌入到可定向曲面Sn和Sm(n≤m),则对任意的整数g,n≤g≤m,图G可嵌入到可定向曲面Sg.因此,图G的最大和最小亏格确定了图G能嵌入的全部可定向曲面.相似的,可定义最大不可定向亏格和最小不可定向亏格.关于图G的最大不可定向亏格(γ)M(G),刘彦佩教授[36],Ringel以及Stahl分别独立地证明了
(γ)M(G)=ε(G)-v(G)+1.
于是,我们只需考虑图在可定向曲面上的最大亏格.
因为图G在任意曲面上的嵌入至少有一个面,由Euler公式易得γM(G)≤[β(G)/2].
其中,β(G)=ε(G)-v(G)+1称为图G的Betti数；[x]表示不超过x的最大整数.若γM(G)=[β(G)/2],则称图G是上可嵌入的.
本论文主要结合图的一些不变量,如最小度,围长,顶点数,独立数,顶点的度和等,研究了图的上可嵌入性以及图的最大亏格的下界,并给出了非上可嵌入的3-正则图的结构特征.具体分为以下七章.
第一章,首先对图在曲面上嵌入的研究背景及发展作了简单介绍.其次,给出了图论的一些基本概念和术语以及图的最大亏格的一些基本性质.
第二章,结合图的最小度和围长,从研究图的给定子图的顶点数出发,我们得到了图的上可嵌入性与顶点数之间的关系.
第三章,结合图的最小度和围长,给出了非上可嵌入连通图的最大亏格的新下界.
第四章,结合图的围长,从研究图的给定子图内相邻顶点的度和出发,得到了图的上可嵌入性与相邻顶点度和的关系.
第五章,结合图的最小度和围长,从研究图的给定子图内独立数,非相邻顶点的度和出发,得到了图的上可嵌入性与独立数,非相邻顶点的度和之间的关系.
第六章,研究了非上可嵌入的2-边连通3-正则图的结构,补充了文献[28]中关于上可嵌入的2-边连通3-正则图的结构.
第七章,提出了一些进一步研究的问题,如计算图的最大亏格嵌入的个数,研究图的相对最大亏格,应用联树方法研究图的最大亏格等.