图的高阶限制边连通度

来源 :兰州大学 | 被引量 : 10次 | 上传用户:Gerryliu1984
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的边连通度和超边连通性常用来度量网络的可靠性,但是当两个图具有相同的边连通度和超边连通性时,就无法对其可靠性进行比较.因此,为了更精确地度量网络可靠性,人们提出了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年的相应结论.
其他文献
本文基于微分方程的有限差分技术以及一致网格增量未知元方法,分别对一维和二维具有时间依赖系数的热方程以及一类一般的三维对流扩散方程进行了不同的研究。由于一致网格增量未知元方法可以很好地降低矩阵条件数,所以该方法的优越性在我们的理论分析和数值实验中都很好地体现了出来。非一致网格作为一种更为灵活的形式,对于许多问题,特别是边界层问题的求解,有着一致网格所无法比拟的优势。相应地非一致网格上的增量未知元方法
图的谱理论是代数图论的主要研究领域之一,涉及图的谱和laplacian谱,前者起源于量子化学.1931年,E.Hückel提出了分子轨道理论,建立了分子轨道能级和分子图的谱之间的联系,大大推动了图的谱理论研究.图的谱理论主要是利用矩阵论,结合组合论和图的结构性质研究图的各种矩阵的谱,讨论这些谱与图的结构性质及图的不变量之间的关系.L.Collatz和U.Sinogowitz的数学论文“Spektr
曲面Fullerene图是嵌入到曲面上的3-正则有限图,它的每个面的边界为5长或6长圈.这样的嵌入只能在球面、环面、克莱因瓶和射影平面上实现,其五边形面的个数分别为12,0,0和6.而球面Fullerene图就是通常的Fullerene图,即碳族Fullerene的分子图.关于Fullerene图的与匹配理论相关的问题已得到广泛关注和研究.本文分四章对曲面Fullerene图进行了研究.我们确定了
本文主要研究E-反演半群的性质和同余,全文共分六章。第一章我们引入并研究了E-反演半群S上的正则同余.同时引入了E-反演半群上的核正规系,证明了S上的每一个正则同余都是由其核正规系所唯一确定的,并用核正规系刻画了E-反演半群S上的正则同余.第二章研究了E-反演半群S上正则同余与其特征迹的关系,确定了具有相同特征迹的最小和最大正则同余.同时也刻画了具有相同特征迹(?)的所有正则同余.建立了S上具有特
本博士论文主要是研究具p(x)-Laplacian算子的在RN中的有界光滑域上的形如下面的椭圆方程问题的解的存在性,多解性及本征值问题。这是一个新的而有趣的课题。本文的特点之一是在边界(?)Ω上有包含|u|p(x)-2u的项。我们根据b(x)的形式,考虑了Robin边值问题与Steklov本征值问题。在Robin边值问题中,根据非线性项h(x,u)的特点,我们分四种情况进行讨论。即,Robin本征
如果图G的一个子图F是G的一个支撑子图,则称F是G的一个因子.Akiyama和Kano将图的因子问题分为两类,分别称为:度因子问题和分支因子问题.如果用因子的度来描述这个因子,则称该因子为度因子.例如,如果一个因子F的所有度都等于1,F是一个1-因子.与此同时,哈密尔顿圈问题可以看成是寻找一个连通的因子使得每个点的度恰好等于2.另一个方面,如果一个因子是用图的概念来描述,则成该因子为分支因子.例如
测度链上动力方程理论不但可以统一微分方程和差分方程、更好地洞察二者之间的本质差异,而且还可以更精确地描述那些有时在连续时间出现而有时在离散时间出现的现象。所以,研究测度链上动力方程既有理论意义,又有现实基础。类似于微分方程和差分方程,非线性项变号的边值问题同样是一个困难且重要的问题。为此,我们研究了测度链上非线性项变号的p-Laplacian奇异多点边值问题正解的存在性。借助于上下解方法和Scha
由于模式和初始场不可避免的误差,气候模拟仍然存在明显误差。本文研究了在这种形势下利用区域气候模拟气候变化,特别是模拟局地的外强迫变化改变引起的气候变化时可能出现的问题。数值试验表明,尽管现有的区域气候模式能够较好地模拟气候的空间分布和季节变化的基本特征,但是用于研究局地外强迫变化的气候效应而进行的敏感性试验时可能造成大的相对误差,使研究结果失去可信性。本文认为在研究外强迫变化的气候效应时,在某些条
这篇博士学位论文主要研究了两类非线性发展方程的动力学行为。一类是带有黏弹性项和非线性项的波方程:我们使用两种不同的方法克服了在[60]中Salim所采用的方法面临的困难,证明了如果黏弹项满足:且那么当初始能量E(0)(2p)/κE(0)时,其中κ是某个正数,则方程(1)的解u(t)在有限时间内依H01(Ω)范数爆破.另外我们利用Salim[63]中的方法
学位
本论文主要研究了毕竟正则半群上的R-unipotent同余和纯整同余、Einversive半群上的正则同余以及周期半群簇子簇格上的同余与算子。具体工作如下:首先利用弱逆把研究正则半群同余的核-迹方法推广到了毕竟正则半群上,分别引入了毕竟正则半群的R-unipotent同余对和纯整同余对,并证明了毕竟正则半群上的R-unipotent同余(纯整同余)由R-unipotent同余对(纯整同余对)唯一确