关于图的最大亏格的一些新研究

摘要

拓扑图论最初是研究怎样把图画在曲面上使得任何两条边互不相交，这个直观的几何问题随着其它数学分支，特别是代数拓扑、群论、组合计数理论以及算法分析等的介入而变得丰富多彩，目前拓扑图论的研究领域可分为两个主流：一是研究图在曲面上嵌入的性质；另一个研究地图计数问题.本文研究属第一个方面，即研究图的嵌入的最大亏格问题. 连通图G在紧的闭曲面S上的嵌入指存在一个同胚映射φ：G→S使得S→φ（G）的每个连通分支都同胚于一个开圆盘，这样的嵌入称为胞腔嵌入.根据S是可定向曲面或者是不可定向曲面，这样的嵌入又分别称为可定向嵌入或不可定向嵌入，图G的最大亏格指图G所能嵌入曲面的亏格中最大的那一个.因为图的任何嵌入必至少含有一个面，由欧拉公式易得图的最大亏格的一个上界：其中符号（）指不超过α的最大整数，｜E（G）｜-｜V（G）｜+1被称为图G=（V（G），E（G））的Betti数并用符号β（G）表示.如果γM（G）=（），则图G被称为上可嵌入的.最大亏格问题起源于Nordhaus、Stewart和White1971年的文章[31]，刘彦佩[21]和Xuong[38]于1979年分别独立地得到了关于图的嵌入的最大亏格的经典定理，随后，由于诸多学者对这一问题的关注与研究使得这一问题取得重大进展.其研究分为两个方面：一是图的上可嵌入性的研究；二是对非上可嵌入图的最大亏格的界的研究.因为任意图在不可定向曲面上总是上可嵌入的，因此最大亏格问题只讨论图在可定向曲面上的嵌入. 在本论文中，一方面，借助已有的研究成果对图的最大亏格问题进行了深入地研究，得出了一些新结果，改进了一些已知结果；另一方面，借助刘彦佩提出的联树法，对最大亏格问题从另一个方面进行了一些尝试性的研究，并取得一些初步进展，本文可分为以下几个部分： 第一章介绍图的最大亏格问题的背景知识以及一些基本概念和术语， 第二章研究了直径-3图中的加边运算与最大亏格. 第三章结合图的围长以及相邻顶点或非邻顶点的度和研究图的上可嵌入性。 第四章研究非上可嵌入图的最大亏格的下界问题. 第五章借助联树模型研究图的最大亏格. 第六章介绍了一些需要进一步研究的问题.

目录

文摘

英文文摘

论文说明：符号说明、图表目录

声明

致谢

第一章 预备知识

§1.1研究背景

§1.2相关的定义与性质

§1.3曲面与联树模型

第二章 直径-3图的加边运算与最大亏格

§2.1相关概念及引理

§2.2主要结果

§2.3关于图的最大亏格下界的结果

第三章 图的上可嵌人性与相邻顶点或非邻顶点度和的关系

§3.1简单图的上可嵌入性与非邻顶点度和的关系

§3.2非简单图的上可嵌入性与非邻顶点度和的关系

§3.3简单图的上可嵌入性与相邻顶点度和的关系

§3.4非简单图的上可嵌入性与相邻顶点度和的关系

第四章 关于最大亏格下界的讨论

第五章 联树模型与图的最大亏格

§5.1概念及引理

§5.2有关最大亏格1-临界顶点的结果

§5.3 图类Pn和Pn*的上可嵌入性

§5.4图类Sn和Sn*的上可嵌入性

第六章 未解决问题

参考文献

作者简历