论文部分内容阅读
图的连通性是图的最基本的性质之一,是图论中重要的研究课题。连通图与网络模型和组合优化联系密切,使它拥有很强的应用背景。连通图中的可去边和可收缩边是探讨图的结构、递归的证明图的某些性质的重要工具,对它们的研究具有重要的理论价值和应用价值。本文选择连通图中的可去边和可收缩边作为研究对象,就是希望通过努力能够对进一步了解连通图的结构以及找出其构造方法的研究工作有所帮助。本文主要研究连通图中可去边和可收缩边的性质以及它们在特定子图上的分布情况。下面简单介绍一下本文的主要结果。对于连通图中的可去边,本文将已有的4连通图中可去边在圈上分布的部分研究成果作了改进,并首次提出了6连通图中可去边的一些性质,主要结果如下:定理2.2.10.设G是4连通图,C为G中任意的圈,若圈C不与G的任何阶为2的边点割断片相交,则C上至少有两条可去边。定理2.3.2.设G是6连通图,|G|≥11,δ(G)≥7,xy∈E_N(G),(xy,S;A,B)为其对应的分离分解,其中x∈A,y∈B,则E(G[S])(?)E+R(G)。定理2.3.3.设G是6连通图,|G|≥11,G的边点割原子的阶至少为3,xy∈E_N(G),(xy,S;A,B)为其对应的分离分解,其中x∈A,y∈B,则E(G[S])(?)E_R(G)。对于连通图中的可收缩边,本文将已有的4连通图中可收缩边在完美匹配上的分布结果进行了改进,并首次给出了5连通图中可收缩边在完美匹配上的分布情况,还得到了一个与6连通图中可收缩边相关的结论,主要结果如下:定理3.2.1.设G是阶大于7的4连通图,M是G的一个完美匹配,且M上的任意一条边不在三角形上,则M上至少有两条可收缩边。定理3.3.2.设G是阶大于9的5连通图,M是G的一个完美匹配,且M上的任意一条边不在三角形上,则M上至少有两条可收缩边。定理3.3.4.设G是阶大于11的5连通图,M是G的一个完美匹配,若图G的任意断片的阶都大子2,则M上至少有两条可收缩边。定理3.4.2.设G是阶至少为8的6连通图,G的任意端片的阶不等于2。设x为G的任意顶点,若与x相关联的每一条边都是不可收缩的,则存在y∈N_G(x),使得d(y)=6,N_G(x)∩N_G(y)≠φ。