论文部分内容阅读
连通图的构造方式在理论和应用中都具有重要的作用,关于连通度较低的连通图的研究已经得到了大量重要结果.连通图的可收缩子图作为讨论连通图结构的一种重要工具,在收缩的子图已知的情况下,我们可以反过来给出图的构造方式.本文对拟5-连通图的构造进行研究,提出了收缩临界拟k-连通图的概念,尝试同时对k-点割和k+1点割的局部结构进行研究.在此基础上,对一些特殊的拟5-连通图的可收缩子图进行了研究,尤其对其可收缩边的数目以及收缩临界拟5-连通图的局部结构.论文主要结论如下:(1)对Bowtie free的拟5-连通图G中每个点周围的4-可收缩边数目进行了讨论,在此基础证明了|E4c(G)|≥|V(G)|+1/2|V5(G)|+1/2|V6(G)|+|V≥7(G)|;(2)证明了一般拟5-连通图中基于度至少为5的顶点数目的4-可收缩边的下界为3/2|V≥5(G)|并说明这个界是最好可能的;(3)证明了若拟5-连通图G的4度点x与4-可收缩边的距离至少为2,则x周围一定存在一个三边形xyz使得xyz收缩之后还是拟5-连通图;(4)证明了4-度点不在三边形内的拟5-连通图中每一个4度点都与一条拟5-可收缩边关联;(5)证明了阶数至少为13的收缩临界极小拟5-连通图的任意圈中都有一个顶点的度至多为5.