论文部分内容阅读
图的连通性是图的最基本的性质之一，同时也是图论中的重要研究课题。除了具备较高的理论价值，图的连通性与网络模型以及组合优化等学科课题也有着密切的联系，加之如今计算机和网络技术发展迅速，使得连通图的研究也具有一定的应用价值。
探讨连通图的结构特征，寻找连通图的构造方法一直是连通图研究的重要课题。随着数学归纳法在图论中的广泛应用，采用递归的方法，利用连通图阶数的”约简”来对其进行研究日益得到重视，即保持图的某种性质，并使图的阶数或边数减少的一系列运算的综合。在这种背景下，图的可收缩边和可去边被定义和广泛研究。本文以连通图中的可去边作为研究对象，以期能够对进一步了解连通图的结构及其构造方法做出贡献。
本文主要研究6连通图中可去边的性质及其在圈和生成树中的分布情况。下面简单介绍一下本文的主要结果。
首先我们给出可去边的定义:
设图G为6连通图，e=xy是图G的一条边。对图G进行以下运算:
(1)从图G中删去边e=xy，得到图G-e。
(2)若存在点u∈{x，y}，使得u在图G-e中是个5度点，则删掉点u，并将点u的5个邻点两两连结为K5。
(3)若经过(1)(2)运算后的图出现重边，则删除重边以单边代替，使之成为简单图。
我们将经过(1)(2)(3)运算得到的图记为G(⊙)e。
如果G(⊙)e仍旧是6连通图，那么边e称为可去边;否则称为可不去边。图G的所有可去边的集合记为ER(G)，所有不可去边的集合记为EN(G)。
本文研究了6连通图中可去边的性质及其在圈上的分布情况，得出下面的结论:
结论1图G为|G|≥11的6连通图，且δ(G)≥7，则G的任意一个圈中至少有两条可去边。
对于6连通图中可去边在生成树和哈密顿圈上的分布情况，我们得到下面两条结论:
结论2图G为|G|≥11的6连通图，且δ(G)≥7，则G的任意生成树中至少含两条可去边。
结论3图G为|G|≥11的6连通哈密顿图，且δ(G)≥7，则G的任意哈密顿圈中至少含三条可去边。