论文部分内容阅读
在通信网络的研宄中,人们通常以图为数学模型表示多处理器系统的互连网拓扑结构,用图的性质和参数来度量网络拓扑的性能.在研宄网络的可靠性时,人们通常用边连通度进行度量.但是用边连通度进行度量有一定的缺陷,基于这一考虑,人们对边连通度进行推广,提出了 m限制边连通度的概念. 设 G是一个无向简单连通图,F是 G的一个边割.如果G- F的每个连通分支至少有m个顶点,那么称F是 G的一个m限制边割.最小m限制边割所含的边数称为G的 m限制边连通度.若 G存在m限制边割,则称G是 m限制边连通图.如果阶至少为2m的连通图G包含一个顶点s,m是整数且m>2,使得G- s的每个连通分支至多有m-I个顶点,则称G是花. 近年来,m限制边连通图得到了众多学者的广泛关注.2009年,王经雨和朱铁丹刻画了周长为3的 m限制边连通图.2011年,他们又刻画了周长为4不含3圈的 m限制边连通图.本文在前人的基础上,刻画了周长和围长均为k的 m限制边连通图,其中k=5或6. 本文共分为三章内容. 第一章首先综述了 m限制边连通图的应用背景和研宄现状,然后介绍了本文中将用到的一些图论基本概念和记号. 第二章研宄了周长和围长均为5的 m限制边连通图,证明了设G是一个周长和围长均为5且阶不小于2m的连通图,则 G含 m限制边割当且仅当G不是花且不属于一类特殊图. 第三章研宄了周长和围长均为6的 m限制边连通图,证明了设G是一个周长和围长均为6且阶不小于2m的连通图,则 G含 m限制边割当且仅当G不是花且不属于两类特殊图.