论文部分内容阅读
图的连通性是图论非常重要的概念之一,图的许多性质和图的连通性有着密切的关系。在图论的研究方法中,我们常常运用一些图的特性的运算,用一些简单的连通图构造出复杂的连通图满足要求的性质。基于此,图的可收缩边运算成为研究复杂连通图的有力工具之一。 本文选择连通图的可收缩边作为研究的对象,考虑5-连通图和7-连通图的可收缩边在不同的特定子图——最长圈、生成树和完美匹配上的分布情况,并得到相应的结果。对于5-连通图,本文首先对5-连通图最长圈上可收缩边的分布的已有成果进行了改进,并首次提出5-连通图生成树上可收缩边的分布情况,得出的主要结论有:定理2.1.3设G是5-连通图,且G中不存在2-断片。P:x=x1x2…xn=y是G的一条最长(x,y)-路。如果路P上任一顶点xi都满足以下条件之一,那么P上至少有两条可收缩边:⑴d(xi)≥6;d(xi)=5,则[V(P)]中无3-圈包含它。定理2.2.1设G是5-连通图,且G中不存在2-断片,H是G的一棵生成树。如果H上的任一顶点xi均满足以下条件之一,则生成树H上至少有一条可收缩边:d(xi)≥6;d(xi)=5,则[V(H)]中无3-圈包含它。对于7-连通图,本文仍然采用树形结构理论进行分类讨论,考虑了7-连通图的可收缩边在最长圈、生成树以及完美匹配上的分布情况,得到的主要结论有:定理3.1.5设G是7-连通图,且G的任意断片的阶都大于3。若C:x=x1x2…xn=y是G的任意最长圈,则C至少包含三条可收缩边。定理3.2.1设G是7-连通图,H是G的一棵生成树。如果G任意一个断片的阶都大于3,那么生成树H上至少包含两条可收缩边。定理3.3.7设G是7-连通图且|G|>15,并且M是G的一个完美匹配,如果M上的任意一条边均不在三角形上,那么M上至少包含两条可收缩边。定理3.3.8设G是7-连通图且|G|>15,M是G的一个完美匹配,如果图G的任意一个断片的阶都大于3,那么M上至少包含两条可收缩边。