无三角图是超限制性边连通的充分条件

发布时间：2017-09-14 02:04

  本文关键词：无三角图是超限制性边连通的充分条件

  更多相关文章： 无三角图 限制性边割 超限制性边连通

【摘要】：为了弥补传统边连通度衡量网络可靠性的的缺陷Esfahanian和Hakimi提出了限制性边连通度的概念.设F是图G的一个边割.如果G-F的每个连通分支都至少包含两个点,那么称F是G的一个限制性边割.如果G的最小限制性边割所含边数等于G的最小边度,那么称G是λ’-优的.如果每个最小限制性边割都孤立图G的一条边,则称G是超-λ’的.本文主要研究无三角连通图的超-λ’性(无三角图是指不包含3-圈的图).第一章介绍了图和网络的基本概念及研究背景.第二章介绍了有关无三角图的定义和主要研究方向.第三章给给出了连通的无三角图是λ’-优图和超-λ’图的充分条件.设G是至少有4个顶点的无三角连通图,任意距离是2的点的点度和的最小值记为τ(G).本文证明如果τ(G)≥2[n+2/]+3,那么图G是超-λ’的.这改进了文献的如下结论：如果τ(G)≥2[n+/2/4]+1.那么图G是λ’-优的.第四章主要研究满足特定条件的图的λ’-超原子的结构.设G是至少有4个顶点的无三角连通图,且满足条件τ(G)≥2 [n+2/4]+1.设X是G的一个λ’-超原子.我们证明了X的导出子图为F列三个图之Km,m,Km,m+1或Km,m+1 - K2且当X的导出了图为Km,m+1 - K2时.[X,X]是包含2m-1条边的边独立集.进一步,我们刻画了所有满足条件τ(G)≥2[n+2/]+1的非超-λ’无三角连通图.
【关键词】：无三角图 限制性边割 超限制性边连通
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 致谢5-6
• 中文摘要6-7
• ABSTRACT7-9
• 第一章 绪论9-13
• 1 基本概念9-10
• 2 准备知识10-11
• 3 研究背景和现状11-13
• 第二章 无三角图13-15
• 1 无三角图的定义13
• 2 无三角图的主要研究方向13-15
• 第三章 无三角图的超-λ’性质15-21
• 1 无三角图是λ’-优的充分条件16-19
• 2 无三角图是超-λ’的充分条件19-21
• 第四章 刻画τ-(G)≥2 [n+2/4]+1的非超-λ’图21-33
• 1 λ'-分片的结构21-26
• 2 构造非超-λ’的λ’-优图26-31
• 2.1 定义原-刘图26
• 2.2 构造非超-λ’的原-刘图26-31
• 3 刻画非超-λ’的原-刘图31-33
• 第五章 结束语33-34
• 参考文献34-36
• 作者简历36-38
• 学位论文数据集38

【相似文献】

中国期刊全文数据库 前10条

1 龙昌满;汪定国;;图的边割的矩阵判别法[J];重庆工学院学报(自然科学版);2008年07期

2 欧见平,张福基;R_m-边割存在的充分条件[J];吉首大学学报(自然科学版);2002年01期

3 李建利;王世英;;R_m-边割存在的一个充分条件[J];太原科技大学学报;2006年06期

4 欧见平;无向二元De Bruijn图的边割计数(英文)[J];内蒙古师范大学学报(自然科学汉文版);2004年01期

5 张秀珍;3连通图边割上的可缩边[J];惠州学院学报(自然科学版);2004年03期

6 唐保祥;任韩;;几类图完美匹配的数目[J];南京师大学报(自然科学版);2010年03期

7 李霄民;李登信;;简化图的一个注记(英文)[J];数学杂志;2011年04期

8 万良霞,刘彦佩;纵横扩张的优化[J];高校应用数学学报A辑(中文版);2003年03期

9 王秀丽;王世英;;k_(p,q)(G)≤λ_(p,p)(G)成立的一些充分条件[J];太原师范学院学报(自然科学版);2009年01期

10 李积庆;欧见平;;无向广义De Bruijn图的m-限制边连通性[J];五邑大学学报(自然科学版);2012年03期

中国硕士学位论文全文数据库 前1条

1 李燕静;无三角图是超限制性边连通的充分条件[D];北京交通大学;2016年

，

本文编号：847218