环-4-连通三正则图的K4,4-图子式排除定理

"这篇论文是关于图论领域的研究，作者周珊来自兰州大学数学与统计学院，发表在2010年4月的《兰州大学学报(自然科学版)》第46卷第2期上，文章编号为0455-2059(2010)02-0066-05。文章主要探讨的是不包含K4,4-图子式的环-4-连通三正则图的结构特征。" 在图论中，一个图被称为三正则图，如果图中的每个顶点都具有相同的度数，即每个节点都有三条边连接。环-4-连通意味着图不仅是连通的，而且任何两个非相邻顶点之间至少有四条独立路径。K4,4-图，也称为立方体图，是一个具有8个顶点和12条边的图，其中每个顶点的度数都是4，且可以看作是四个全等的K4（完全图）通过共享边连接起来的图形。图的子式是指可以通过删除或收缩边和顶点得到的图。 文章的核心成果是证明了如果一个环-4-连通三正则图不包含立方体图（K4,4）作为其子式，那么这个图要么同构于Vn（n大于6的圆柱图），要么同构于著名的Petersen图。Petersen图是一个具有10个顶点和15条边的三正则图，它既不是环-4-连通的，也不包含K4,4子式。Möbius带是一种特殊的双层图，类似于数学上的Möbius带形状，也是环-4-连通三正则图的一个例子。 基于这个证明，作者将所有不包含K4,4-图子式的环-4-连通三正则图分为三大类：Petersen图、Möbius带以及一类由论文作者定义的特殊图。这里的“特殊图类”可能是指除了已知的Petersen图和Möbius带之外，满足特定条件的新图构造。 图子式在图论中扮演着重要的角色，因为它们可以用来描述图的结构属性和复杂性。Kuratowski定理指出，一个图是平面的当且仅当它不包含K3,3（Kuratowski子图）和K5（五角图）作为子图。类似地，不包含K4,4子式的环-4-连通三正则图的分类可以帮助我们理解这些图的几何和拓扑特性。 点分裂和把手是图操作的术语。点分裂是指将一个顶点分割成两个顶点，使得原顶点的邻接边分别连接到新顶点，而把手通常指的是一类具有特定连接性的图结构。这些操作在构建和分析图的子结构时是常见的工具。 该论文的贡献在于提供了对特定类型图的深入理解，特别是那些不包含特定子图结构的图，这对于图论的理论研究和应用，如网络设计、编码理论以及算法设计等具有重要意义。