关于图的可定向嵌入亏格分布

摘要

已知一个连通图G和一个闭曲面S(无边缘的2-维紧流形)，若存在一个同胚φ：G→S使得S-φ(G)的每一个连通分支都同胚于一个开圆盘，则称G在S上有一个胞腔嵌入。若S是可定向的，则嵌入是可定向嵌入；若S是不可定向的，则嵌入是不可定向嵌入。图的曲面嵌入问题是拓扑图论的中心问题。在本论文中图，曲面和嵌入分别指的是连通图，闭曲面和可定向的胞腔嵌入. 已知一个图G，G的亏格指的是它所能嵌入的曲面的最小亏格。图在各种不同亏格的曲面上有多少个不同的嵌入呢?这就是图的嵌入亏格分布问题。由于求图的亏格是NP-完备的，由此可见图的嵌入亏格分布问题的难度和意义。 Gross和Furst在1987年引入了图的嵌入亏格分布的概念。迄今为止，只求出以下图类的嵌入亏格分布： closed-end ladders，circular ladders，MSbius ladders，Ringel ladders，dipoles，cobblestone paths，bouquets ofcircles和necklaces.所用的方法主要是组合的方法，Jackson公式法和Mohar覆盖矩阵法。总体而言，这些方法对解决其它图的嵌入亏格分布有局限性。 2003年刘提出的图的联树(1979的文章体现了这种思想)为嵌入亏格分布的研究提供了理论基础。 在本论文中，我们引入了图的嵌入曲面和曲面集的亏格分布的概念。通过运用图的联树我们提取了图的嵌入曲面，从而提出了两种新方法。一个是曲面生成法即利用嵌入曲面间的生成关系求图的嵌入亏格分布的方法；另一个是曲面分类法即通过分类曲面利用曲面集的关系计算图的嵌入亏格分布的方法。通过使用新方法和下面的新的研究结构对图的嵌入亏格分布问题展开了系统化的研究： (1)梯图和交叉图(2)梯型图和交叉型图(3)含有Hamilton路的3-正则图(4)3-正则图(5)一般图它们的包含关系如下： 我们得到了梯图和交叉图的嵌入亏格分布的显式表达式，把已知的circular ladders，Mobius ladders，closed-end ladders，Ringel ladders的嵌入亏格分布简单地推出，得到了其它四类图的嵌入亏格分布，这是对于这些图类的第一个结果． 总之，这些新方法不仅推出了一些已有的结果而且可以用来研究其它的嵌入问题。

目录

文摘

英文文摘

ACKNOWLEDGEMENTS

Chapter 1 Introduction

1.1 Situation of the problem

1.2 Organization of this dissertation

Chapter 2 Preliminaries

2.1 Sequences and surfaces

2.2 Graphs and embeddings

2.3 Joint trees and embedding surfaces

2.4 Genus distribution and embedding genus distribution

Chapter 3 Two types of graphs with the same embedding genus distribution

3.1 Embedding genus distribution in the first type of graphs

3.2 For graphs in the second type

3.3 Generalization

Chapter 4 Embedding genus distribution for ladder type and cross type

4.1 Genus distribution for ladder type and cross type

4.2 Embedding genus distribution for ladder type and cross type

4.3 Genus distribution for certain type of surface sets

4.4 Embedding genus distribution for certain type of graphs

4.5 Embedding genus distribution for a type of non-planar graphs

Chapter 5 Embedding genus distribution for a cubic graph with a Hamilton path

5.1 Genus distribution of some surface sets

5.2 Embedding genus distribution of a cubic graph with a Hamilton cycle

5.3 Embedding genus distribution of a cubic graph with a Hamilton path

Chapter 6 Embedding genus distribution for a graph

6.1 Genus distribution of some surface sets

6.2 Embedding genus distribution for a cubic graph

6.3 Embedding genus distribution for a graph

Chapter 7 Dissertation for further study

Bibliography