关于图的k阶限制边连通度一些问题的研究

来源 :山西大学 | 被引量 : 0次 | 上传用户:hymalong
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的限制连通性问题一直是图论的一个核心课题.由于限制连通度能度量网络的可靠性和容错性,伴随着互连网络的快速发展,近年来对图的限制连通性进行了广泛研究.设G=(V, E)是有限简单无向图,其中V=V(G)和E=E(G)分别是G的顶点集和边集.设S是连通图G的一个边割,若G-S的每个连通分支都至少有k个点,则称S是G的一个k-限制边割.称G中所含边数最少的k-限制边割为λk-割.记G的k-限制边连通度λk=λk(G)为λk-割所含的边数.定义ξk(G)=min{|[X,(X)]|:X(C)V(G),|X|=k,G[X]是连通子图},若λk(G)=ξk(G),则称G是λk-最优图.  在本文中,我们主要研究几类图限制边连通度的一些问题.本文共分三章:  第一章,介绍了文章所涉及的一些概念、术语和符号.  第二章,给出了λ5-最优图的一个充分条件.主要结果如下:  设G是一个v≥17,δ≥([)v/2」-4且λ5(G)≤ξ5(G)的λ5-连通图,若  (i)G中每个导出六圈以及任意由一条边相连的两个三角形的粘合图中都存在非粘合点u满足d(u)≥([)v/2」-2;  (ii)G中每个导出五圈以及任意两个三角形的粘合图中都存在非粘合点v满足d(v)≥([)v/2];  (iii)G中每个四圈上都存在一点w满足d(w)≥([)v/2」+4,则G是λ5-最优图.  第三章,给出了λ4-最优图的一个度条件.主要结果如下:  设G是一个v≥11的λ4-连通图,若  (i)对于任意x,y∈V(G),当d(x,y)=4时,max{d(x),d(y)}≥([)v/2」-3;  (ii)对于任意x,y∈V(G),当d(x,y)=3时,max{d(x),d(y)}≥([)v/2」-1;  (iii)对于任意x,y∈V(G),当d(x,y)=2时,max{d(x),d(y)}≥([)v/2」+1;则G是λ4-最优图.
其他文献
时下,在干部队伍中有一种值得注意的现象,就是有些人讲起成绩来是浓墨重彩,建了这个工程,上了那个项目,形势一片大好,而说起问题来又是一大堆,工资没钱发,投资尚有缺口,生产
学位
数字水印(Digital watermark)技术作为信息安全的一种重要手段,主要用于数字产品的版权保护,并得到广泛的研究和应用.它通过在原始数据中嵌入秘密信息来证实该数据的所有权或
贝叶斯阴阳(BYY)谐和学习理论是一种崭新的统计学习理论与方法,可直接应用于混合高斯模型的建模及其聚类分析.这种学习机制是通过优化混合高斯模型上的一个和谐函数来实现的,
目的:研究港币在澳门的流通情况,分析其流通可能受哪些因素的影响。方法:对澳门的港币流通情况进行定性分析,并收集流通量数据和贸易量、博彩消费收入等数据,在ADF检验和Gran
2011年前三个季度,我国金融市场继续保持健康平稳运行。主要特点是:股票市场规模继续稳步扩大,成交量逐季下滑,股指在年初小幅走高后呈震荡走低态势;债券市场融资活跃,融资成
针对煤矿井下泵房监控系统中的液位监控具有非线性、上升时间长与反应滞后现象的特点,提出了采用九点控制器的方法进行水泵控制,该方法是根据控制行为(偏差和偏差变化率)来调
利用上下解的方法,本文主要研究了一类二阶微分方程的周期边值问题,给出了正解存在的充分条件.全文共分三部分:第一章简要介绍了微分方程边值问题的研究背景和研究现状及本文的
对于我们提出的这个新模型,首先要解决,也是必须解决的问题是,我们提出的反问题是不是合理的?或者说,我们给出的附加条件是否可以唯一地确定每个点热源的具体位置,该热源的组
大部分小学生对于写作总是谈“作”色变.有的无从下笔,有的干脆誊抄例文——“拿来主义”.其实小学阶段的习作是写话、写作,不是创作.只要会说话,会写字就可以写出文章.只不