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

论文摘要

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

论文目录

• 摘要
• Abstract
• 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