收缩临界κ连通图中低度顶点的研究

"The Vertices of Lower Degree in Contraction-Critical κ Connected Graphs" 这篇论文主要研究的是图论中的一个特定概念——收缩临界κ连通图。在图论中，一个图G被认为是κ连通的，如果从图G中删除任意κ-1个顶点后，剩下的图仍然是连通的。而“收缩临界”指的是经过一次或多次顶点收缩操作（将两个相邻的顶点合并为一个顶点）后，图的连通性会降低的情况。 作者袁旭东、李婷婷和苏建基来自广西师范大学数学系。他们关注的问题是收缩临界κ连通图中度数较低的顶点。已知的一个结果是，对于这样的图G，其最小度数不超过$\lfloor\frac{5\kappa}{4}\rfloor - 1$，这个结论在《图论与组合》期刊1991年的一篇文章中有提及。 在这篇论文中，作者进一步探讨了当图G中最多只有一个度数为κ的顶点时的情况。他们证明了在这种情况下，G不可能存在一对相邻的顶点，使得这两个顶点的度数都小于等于$\lfloor\frac{5\kappa}{4}\rfloor - 1$。或者，如果存在一个度数为κ的顶点，其邻域内必须有一个顶点的度数小于等于$\lfloor\frac{4\kappa}{3}\rfloor - 1$。 此外，他们还解决了苏建基之前提出的一个猜想。当图G的最小度数等于$\lfloor\frac{5\kappa}{4}\rfloor - 1$，并且κ能被4整除时，G应该有κ个度数为$\lfloor\frac{5\kappa}{4}\rfloor - 1$的顶点。他们证实了这个猜想是正确的，并且指出G还有$\frac{3\kappa}{2}$个具有同样度数的顶点。 关键词包括：收缩临界图、片段（Fragment）、N(B)-片段。 1. 引言 文章的引言部分通常会简要介绍图论的基础知识，比如定义了图的基本元素（顶点集V和边集E），并概述了研究背景和目标。它可能还会提到前人在这方面的工作以及尚未解决的问题，从而引出本文的研究内容。 这篇论文深入探讨了收缩临界κ连通图的性质，特别是关于这些图中低度数顶点的分布和交互关系，这对理解图的连通性和结构有着重要的理论价值。这些发现对于图的理论研究，如图的剪枝、连通性分析和算法设计等方面，都有实际的应用意义。