图的上可嵌入性与3-正则图的最大亏格

摘要

本篇论文主要研究了拓扑图论中的一个十分活跃的方面——图的上可嵌入性和最大亏格，它是图的曲面可嵌入性理论的一个重要研究课题。图的曲面可嵌入性起源于著名的四色问题。自从Cayley1878年正式公布了四色问题后，图的平面可嵌入性问题便开始引起了人们的关注。1890年Heawood对一般的曲面提出了类似的地图着色问题后，图的曲面可嵌入性问题便进一步提出来了，特别是Hilbert和Cohn-Vossen将四色问题化为确定Kn的引线问题(Kn的引线问题等价于求其亏格)。虽然，地图着色问题于1968年得到解决，它的解法却导致了一个新的数学分支——拓扑图论的产生，图的曲面可嵌入性就成了这一数学分支的一个主要研究内容。这里的图是指连通图，曲面是指一个连通紧致的2维闭流形(可定向或不可定向均可)。图的一个嵌入是指存在一个从图到曲面的拓扑映射使从曲面上去掉图的顶点和边后的每个连通分支都拓扑同胚于一个开圆盘，这样的嵌入也称为2-胞腔嵌入。图的(最小)亏格γ(G)是指最小的整数g使之在曲面Sg有2-胞腔嵌入，而图的最大亏格γM(G)是指最大的整数g使之在曲面Sg有2-胞腔嵌入。图的亏格具有介值性质，即对于最小亏格和最大亏格之间的任一整数g存在图G在Sg上的2-胞腔嵌入。达到最大亏格上界的嵌入称为上可嵌入。由于已经证明了任一连通图在不可定向曲面上的最大亏格等于其圈秩，因此这里关于曲面上可嵌入性的讨论均指是在可定向曲面上。 拓扑图论不仅丰富了拓扑学的内容，也使图论的面目一新，使人们对图和曲面有了更为深刻的认识。考虑到图在曲面上的上可嵌入性及图的一些性质如边连通度、独立集和独立数、3-正则等以及N.Xuong1979年、L.Nebesky1981年分别给出的图的上可嵌入性的两个充要条件，本文主要利用了黄元秋1999年给出的非上可嵌入图的结构特征，给出了一些新的上可嵌入图类，使图论中的一些上可嵌入性问题得到了解决。本篇论文作了以下主要工作： 1、结合边连通度，探讨了独立集中具有最小特定度和的上可嵌入图类。 2、刻画了边连通简单图中具有特定最小度的上可嵌入图类。 3、讨论了边连通简单图的独立数与上可嵌入性的关系。 4、探讨了v≥6的连通3-正则图的最大亏格和上可嵌入性。 5、得到了连通3-正则简单图当γM(G)=v/6+1(v=|V(G)|≥18)时的结构特征。

目录

文摘

英文文摘

学位论文独创性声明及学位论文使用授权声明

第一章概述

§1.1图的最大亏格与上可嵌入的由来

§1.2基本概念

§1.3图的最大亏格与上可嵌入性的已有结果

§1.4本文的主要结果

第二章独立集中具有最小特定度和的点的上可嵌入图类

§2.1引言

§2.2基本知识与基本引理

§2.3边连通简单图中具有最小特定度和的上可嵌入图类

§2.4边连通简单图中具有特定最小度的上可嵌入图类

第三章边连通简单图的独立数与上可嵌入性

§3.1引言

§3.2已知的结论

§3.3边连通简单图的独立数与上可嵌入性的关系

第四章连通3-正则图的最大亏格与上可嵌入性

§4.1引言

§4.2连通3-正则图的最大亏格的已知结果

§4.3最大亏格为γM(G)=v/6+1的连通3-正则图的结构特征

参考文献

作者申请硕士学位期间完成的工作

致谢