论文部分内容阅读
连通度和边连通度是衡量网络可靠性的一个重要参数。作为经典连通度的推广,人们提出了条件(边)连通度。本文主要研究一些重要图类的条件(边)连通度。
第一章介绍了背景和一些基本概念。第二章主要研究Bi-Cayley图的超边连通性和最优超边连通性。设G是一个有限群,S(可以含有单位元)是G的一个子集,则Bi-Cayley图是一个以G×{0,1}为点集,{{(g,0),(gs,1)},g∈G,s∈S}为边集的二部图。若图X的每个最小边割均是某个点的关联边集,则称图X为超边连通的。图X的满足去掉它后每个连通分支都至少有两个点的边割的最小基数称为图X的限制边连通度。一个k-正则图X被称为最优超边连通的,若X是超边连通的且X的限制边连通度达到最大2k-2。在第二章中,我们证明了除偶圈外,所有连通Bi-Cayley图都是最优超边连通的。第三章研究轨道数为2的k-正则连通图的边连通度,得到了如下结果:(1)确定了轨道数为2的3-正则和4-正则连通图的边连通度;(2)证明了对于给定的正整数k和m,轨道数为2的k-正则m-边连通图的存在性;(3)在围长大于等于5的前提下,轨道数为2的k-正则连通图的边连通度为正则度k。
第四章研究线图和有向线图的第二等周点连通度,得到了如下结果:(1)最小度大于等于2的强连通有向线图的第二等周点连通度等于它的点连通度;(2)对于无向线图,我们给出了第二等周点连通度存在的充要条件;(3)对于第二等周点连通度存在的无向线图,它的第二等周点连通度或者等于限制点连通度或者等于最小度和次最小度的和。