（n-4）—正则图的约束数的界

发布时间：2017-08-18 20:43

  本文关键词：（n-4）—正则图的约束数的界

  更多相关文章： 约束数 控制数 反证法 (n-4)-正则图

【摘要】：图的约束数概念最早是作为衡量网络连接失败脆弱性的一个重要参数由Fink et al在1990年正式提出的,由于图的约束数问题的解决依赖于图的控制数,而图的控制数是图论中一个经典而重要的内容,受到学术界的广泛关注,因而对图的约束数问题的研究具有很大的学术价值.同时,由于一般图的控制数问题很早之前就被Garey和Johnson[2]证明是NP-完全的,因此要解决任意图的约束数问题也是非常困难的.但对于一些特殊结构的图,已经有很多很好的成果.正则图作为一类特殊的图,其约束数问题的解决自然会引起关注.在文献[10]中,Fink et al证明了b(Kn)=「n/2]；b(Kn1,n2,n3…,nt)=2t-1,其中n1=n2=n3=…=nt=2.在2012年,Hu和Xu[3]证明了对于任意的(n-3)-正则图均有b(G)=n-3.然而对于k-正则图(3≤k≤n-4),这些正则图的约束数的值的研究还没有取得任何进展.本文遵循此思路,重点研究(n-4)-正则图的约束数问题.本文共有四章内容,主要是研究(n-4)-正则图的约束数问题.第一章给出了文章用到的基本概念,已有的结论以及主要结果.第二章主要证明：任意(n-4)-正则图的控制数为2,且其约束数的上界为(n-4).第三章主要证明：(n-4)-正则图约束数的下界为(n一7).最后一章节主要给出了一些值得继续深入研究的问题.
【关键词】：约束数 控制数 反证法 (n-4)-正则图
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要5-6
• Abstract6-7
• 第1章 绪论7-9
• 1.1 基本概念7-8
• 1.2 k-正则图的约束数问题及已有的结论8
• 1.3 本文的主要研究结果8-9
• 第2章 (n-4)-正则图的约束数的上界9-11
• 2.1 (n-4)-正则图的控制数9-10
• 2.2 本章主要结论10-11
• 第3章 (n-4)-正则图的约束数的下界11-46
• 3.1 本章主要结论11-12
• 3.2 引理证明12-19
• 3.3 定理证明19-46
• 第4章 可进一步研究的问题46-47
• 参考文献47-48
• 致谢48

【相似文献】

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

1 宋晓新;关于3正则图的三匹配交猜想(I)[J];数学研究;2002年04期

2 宋晓新;关于3正则图的三匹配交猜想 (Ⅱ)(英文)[J];数学季刊;2002年04期

3 严谦泰;关于2K阶K正则图强协调性的研究[J];安阳师范学院学报;2003年02期

4 严谦泰;关于5-正则图的强协调性[J];大学数学;2003年02期

5 闫桂英,许保光,吉日木图;关于3-正则图的路分解[J];系统科学与数学;2004年02期

6 钟波,谢挺;关于正则图的路分解[J];西华大学学报(自然科学版);2005年04期

7 周后卿;徐立新;;正则图的强积的秩[J];吉首大学学报(自然科学版);2007年01期

8 梁志和;;完全图循环分解成2-正则图[J];应用数学学报;2008年06期

9 南小康;;3-正则图的1-因子与割边数[J];兰州大学学报(自然科学版);2008年S1期

10 李光暖;许宝刚;;关于正则图存在平衡划分的一些结果[J];高校应用数学学报A辑;2009年03期

中国重要会议论文全文数据库 前2条

1 ;Hamilton Circuits in Cubic Polyhex Graphs[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

2 师海忠;;正则图连通圈:多种互连网络的统一模型[A];中国运筹学会第十届学术交流会论文集[C];2010年

中国博士学位论文全文数据库 前6条

1 文飞;若干图类的谱特征问题研究[D];新疆大学;2015年

2 程希明;只有三个不同特征值的图[D];中国科学技术大学;2016年

3 汪定国;正则图的独立集与团横贯[D];上海大学;2013年

4 张翠;s-正则图和Hamilton图[D];北京交通大学;2011年

5 刘奋进;图邻接谱确定问题的一些研究[D];新疆大学;2012年

6 邵泽辉;Ramsey理论中图的构造与计算[D];华中科技大学;2008年

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

1 秦艳丽;9度1—正则Cayley图的分类[D];广西大学;2015年

2 李玉萍;三正则双轨道图的连通性和极大非正则图[D];新疆大学;2015年

3 王兆;五正则图的斜能量研究[D];青海师范大学;2015年

4 严卉;（n-4）—正则图的约束数的界[D];南京师范大学;2015年

5 颜娟;第Ⅱ类正则图的色特征[D];新疆大学;2006年

6 兰培挺;一些4-正则图最优扩张的演化[D];北京交通大学;2007年

7 赵承业;三正则图及其相关图的交叉数问题[D];大连理工大学;2002年

8 王丹;正则图的交叉数[D];大连理工大学;2002年

9 郝欣;具有相同路径层矩阵不同构的r-正则图[D];大连理工大学;2004年

10 周后卿;正则图在某些二元运算下的秩[D];湖南师范大学;2006年

，

本文编号：696696