Bi-Cayley图与半传递图的连通性

论文摘要

随着信息网络的飞速发展,许多相关的理论问题开始引起人们的重视,其中之一是网络的可靠性,即网络在它的某些部件（节点或者连接）发生故障的条件下仍能工作的能力。网络拓扑结构通常被模型化为图,因此,图论中的一些经典概念,如连通度和边连通度,就被用来研究网络的可靠性。为了进一步研究,人们提出了各种各样的高阶连通性的概念,如super ?κ性（super ?λ性）, r-限制性边连通度等。本文研究Bi-Cayley图和半传递图的各种连通性问题。第一章,我们介绍了研究背景和一些基本概念,给出了Bi-Cayley图和半传递图的定义,并对各类连通度问题研究的历史与现状进行了一定程度的综述。第二章,我们研究这两类图的连通度问题,证明了所有连通Bi-Cayley图和半传递图的连通度达到其最小度。第三章研究这两类图的超点连通性问题。我们证明了一个连通点传递二部图不是super?κ的当且仅当它同构于一个圈Cn与一个空图Nm的字典积（其中n≥6,m≥1）,并且刻画了非hyper?κ的连通点传递二部图。另外,我们还刻画了非hyper?κ的连通半传递图并得出了连通半传递图是super ?κ的两个充分条件。第四章研究高阶边连通性问题,获得了如下结论:（1）所有连通半传递图都是super ?λ的;（2）所有至少包含4个顶点的连通k-正则半传递图都是最优-λ的;（3）给出了连通Bi-Cayley图是最优-λ（3）的一个充要条件。本文研究中,各种原子的概念及其不交性质是我们进行论证的关键,证明中使用的主要方法是反证法。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究背景
• 1.2 基本概念
• 1.3 研究综述
• 第二章 Bi-Cayley 图与半传递图的连通度
• 2.1 原子和非本原块
• 2.2 Bi-Cayley图的连通度
• 2.3 半传递图的连通度
• 第三章 点传递二部图与半传递图的超点连通性
• 3.1 概念和术语
• 3.2 点传递二部图的super-κ性和hyper-κ性
• 3.3 半传递图的super-κ性和hyper-κ性
• 第四章 Bi-Cayley 图与半传递图的高阶边连通性
• 4.1 super-λ半传递图
• 4.2 半传递图的最优-λ性
• 4.3 最优-λ（3）Bi-Cayley图
• 参考文献
• 博士在读期间发表论文清单
• 致谢