图的高阶限制边连通度

论文摘要

图的边连通度和超边连通性常用来度量网络的可靠性，但是当两个图具有相同的边连通度和超边连通性时，就无法对其可靠性进行比较．因此，为了更精确地度量网络可靠性，人们提出了m-限制边连通度的概念：设m是正整数，连通图G的边割S称为m-限制边割，如果G-S的每个连通分支都至少包含m个顶点：G中最小m-限制边割的基数称为图G的m-限制边连通度，记为λm（G）．当m=2时，λ2（G）称为图G的限制边连通度，通常记为λ’（G）．如果λm（G）存在，则称G是λm-连通图．目前，关于m-限制边连通度方面的研究，主要集中在讨论m-限制边连通度的存在性及上界，计算特殊图类或网络的m-限制边连通度，寻求分别具有极大m-限制边连通度和较少最小m-限制边割数的图类等方面．令ξm（G）：=min{|[X,X]|：X（?）V（G）,|X|=m，且G[X]连通}．如果图G的m-限制边割S=[X，X]满足|X|=m或|X|=m，则称S是平凡的．设λm-连通图G满足λm（G）≤ξM（G），如果λm（G）=ξM（G），则称G是最优m-限制边连通图，简称λm-最优图；如果G的每个最小m-限制边割都是平凡的，则称G是超级m-限制边连通图，简称超-λm连通图．一般来说，λm-最优图和超-λm连通图具有较高的可靠性．本文共分五章，第一章综述m-限制边连通度的应用背景及研究进展，介绍本文用到的一些基本概念，术语和记号，并概述本文的研究内容及获得的主要结果．第二章主要研究满足λm（G）≤ξm（G）的一个一般充分条件．已经证明，当m≤3时，λm-连通图G具有λm（G）≤ξm（G）这一性质．当m≥4时，Bonsma等人指出不等式λm（G）≤ξm（G）一般不再成立．欧见平于2007年证明阶大于等于11的λ4-连通图G满足λ4（G）≤ξ4（G）．本章我们通过研究满足λm（G）>ξm（G）的λm-连通图所具有的结构性质，不仅易得欧见平的以上结论，而且还得到了如下结论：当m≥5时，阶大于m（m-1）的λm-连通图G均满足λm（G）≤ξm（G）．最后，通过构造例子来说明我们给出的条件是最好的．第三章主要研究图的最优限制边连通性．给出并证明一般图，二部图，以及直径为2的图分别是λ’-最优图的充分条件，同时通过构造例子来说明这些条件不能被减弱．本章得到的结论是对Hellwig与Volkmann 2004和2005年相应结论的改进，其中关于直径为2图的λ’-最优性结论是对王应前和李乔1999年结论的进一步推广．第四章主要研究图的超级限制边连通性．给出并证明一般图，二部图，无三角形图，以及直径为2的图分别是超-λ’连通图的充分条件，并用例子说明这些条件是最好的．本章所得的结论推广了王应前和李乔2001年的结论．而关于直径为2图的超-λ’连通性，在不含三角形的条件下，我们得到的推论与王世英和林上为2007年的结论类似，并且推广了范英梅2003年的结论．第五章主要研究图的λ3-最优性和超-λ3连通性．首先讨论λ3-最优与λ’-最优和超-λ’连通之间的关系．然后给出并证明一般图，二部图，无三角形图，以及直径为2的图分别是λ3-最优图和超-λ3连通图的充分条件，并通过构造例子来说明这些条件不能被减弱．最后证明最小度δ≥2m的超-λm连通非完全图所具有的一个结构性质：G的最小度顶点集M的导出子图G[M]不含完全子图Kδ-m+1．本章中，我们把欧见平2003年关于无三角形正则图的λ3-最优性结论推广到一般图．另外，关于直径为2图的λ3-最优性和超-λ3连通性，我们所获得的结论推广了王应前2006年的相应结论．

论文目录

• 摘要
• Abstract
• 第一章 引言
• §1.1 m-限制边连通度的应用背景及研究进展
• §1.2 基本概念,术语和记号
• §1.3 本文的研究内容及主要结果
• m（G）≤ξ_m（G）的一般充分条件'>第二章 λ_m（G）≤ξ_m（G）的一般充分条件
• §2.1 引言
• m（G）>ξ_m（G）图的结构性质'>§2.2 满足λ_m（G）>ξ_m（G）图的结构性质
• m（G）≤ξ_m（G）的一般充分条件'>§2.3 λ_m（G）≤ξ_m（G）的一般充分条件
• 第三章 λ'-最优图的充分条件
• §3.1 引言
• §3.2 一般的λ'-最优图
• §3.3 λ'-最优二部图
• §3.4 直径为2的λ'-最优图的进一步研究
• 第四章 超-λ'连通图的充分条件
• §4.1 引言
• §4.2 一般的超-λ'连通图
• §4.3 超-λ'连通的二部图和无三角形图
• §4.4 直径为2的超-λ'连通图
• 3最优性与超-λ₃连通性'>第五章 图的λ₃最优性与超-λ₃连通性
• §5.1 引言
• 3-最优与λ'-最优和超-λ'连通的关系'>§5.2 λ₃-最优与λ'-最优和超-λ'连通的关系
• 3-最优图和超-λ₃连通图的充分条件'>§5.3 一般λ₃-最优图和超-λ₃连通图的充分条件
• 3-最优图和超-λ₃连通图'>§5.4 无三角形的λ₃-最优图和超-λ₃连通图
• 3-最优和超-λ₃连通二部图的充分条件'>§5.5 λ₃-最优和超-λ₃连通二部图的充分条件
• 3-最优图和超-λ₃连通图'>§5.6 直径为2的λ₃-最优图和超-λ₃连通图
• m连通图的一个性质'>§5.7 超-λ_m连通图的一个性质
• 参考文献
• 在读期间完成的主要论文
• 致谢