k元n方体和OTG图的H-强迫数

发布时间：2017-09-20 01:18

  本文关键词：k元n方体和OTG图的H-强迫数

  更多相关文章： H-强迫集 H-强迫数 k元n方体 Ore定理 弱闭包

【摘要】：在图理论中,哈密尔顿圈问题一直是人们重点关注的问题.G的一个圈称为哈密尔顿圈,如果它包含G中所有点.图G称为一个哈密尔顿图如果它包含一个哈密尔顿圈.若G是一个哈密尔顿图,对于非空顶点集X(?)V(G),如果每个包含X的圈都是哈密尔顿圈,则X称为G的H-强迫集.最小的H-强迫集的顶点个数称为G的H-强迫数.H-强迫数和H-强迫集这两个概念是由I.Fabrici等人在2009年提出的概念.因为这个概念对于研究图的哈密尔顿性有重要意义,所以这一概念一经提出就引起了人们的广泛关注.k元n方体,是一种特殊的拓扑网络模型,记为Qkn(k≥1,n≥1)它有kn个顶点,每个顶点可以记为u=un-1un-2...u0,其中ui∈{0,1,...k-1},0≤i≤n-1.顶点u=un-1un-2...u0和顶点u=un-1un-2...u0相邻当且仅当存在一个整数J,0≤j≤n-1,使得uj=uj±1(mod k)且对每个i∈{0,1,...,j-1,j+1,...,n-1}都有ui=vi.对于G中每一对不相邻的顶点u,v,如果d(u)+d(u)≥n,则称G满足了Ore定理的条件.为了方便,用OTG表示一个满足Ore定理条件的图.Ore证明了任意一个OTG都是哈密尔顿图.本文研究的是网络拓扑图k元n方体Qkn和OTG图的H-强迫集和H-强迫数,通过分析图形结构及分类归纳来得到结论.本文分为四章.第一章是绪论,介绍了本文的研究背景及相关结论.第二章是基本概念,介绍了本文将要用到的术语和概念.第三章通过研究Cm×Cn的H-强迫数,得出网络拓扑图k元n方体Qnk的H-强迫数.分别得到三个主要的结论：(i)设G=Cm×Cn(m2,n2),则(ii)设G=Qkn(n≥2,k2),则(iii)设G=Pn×Pn (n≥4,且n为偶数),则h(G)=n2/2-2.第四章研究了OTG图的H-强迫数和最小H-强迫集.通过研究这类图的弱闭包得到这一类图的H-强迫数为n或n-2或n/2,并由此给出了这类图的一个划分,得到了下面的结论：设G是一个OTG且有n≥5个顶点,X是G的最小H-强迫集.令Cω(G)是G的弱闭包,S是Cω(G)的最大独立集.则(1)H-强迫数h(G)=n-2或n/2或n.(2)其中x,y ∈V(G)且dCw(G)(x)=n-1,dCw(G)(y)=n-1.
【关键词】：H-强迫集 H-强迫数 k元n方体 Ore定理 弱闭包
【学位授予单位】：山西大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要6-8
• Abstract8-10
• 第一章 绪论10-12
• 第二章 基本概念12-15
• 第三章 k元n方体Q_n~k的H-强迫数15-23
• §3.1 准备知识15-16
• §3.2 主要结论16-19
• §3.3 其他结论19-23
• 第四章 OTG图的H-强迫数23-36
• §4.1 准备知识23-25
• §4.2 主要结论25-36
• 参考文献36-38
• 研究成果38-39
• 致谢39-41
• 个人简况及联系方式41-42
• 承诺书42-43

【共引文献】

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

1 白亚兰;师海忠;;完全二叉树到星连通圈网络的嵌入[J];甘肃科学学报;2014年03期

2 杨玉星;王世英;;k元n立方网络的k圈排除问题的递归算法[J];计算机应用;2013年09期

3 李瑞娟;张文娟;;圈和路的笛卡尔积的H-强迫数[J];中北大学学报(自然科学版);2013年05期

4 周后卿;周琪;;循环图的Kirchhoff指标[J];华中师范大学学报(自然科学版);2014年02期

5 张淑蓉;王世英;董操;;边故障k元n立方体的超级哈密顿交织性[J];计算机工程与应用;2014年21期

6 郑丽丽;李海东;;折叠超立方体网络的自适应诊断[J];河南工程学院学报(自然科学版);2014年04期

7 高珊;;匹配组合网络的宽直径[J];湖北大学学报(自然科学版);2015年01期

8 张国珍;;单向k-元n-立方体网络[J];计算机工程与应用;2015年20期

9 李瑞娟;李丽;;两类图的H-强迫数[J];山西大学学报(自然科学版);2013年04期

10 张欣;师海忠;;交叉立方体连通圈网络的Hamilton分解[J];软件;2015年08期

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

1 王岩;扭立方体和奇偶立方体上独立生成树的嵌入研究[D];苏州大学;2014年

2 沈华;基于Petri网的Web服务组合性能评价体系的研究[D];武汉大学;2013年

3 王凡;超立方中匹配的哈密尔顿圈扩张问题的研究[D];兰州大学;2014年

4 洪振木;某些网络可靠性和有效性研究[D];中国科学技术大学;2014年

5 刘艳霞;基于代数图论的复杂网络的拓扑性质和构造方法研究[D];华南理工大学;2013年

6 程冬琴;若干互连网络的圈嵌入和路嵌入[D];北京交通大学;2015年

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

1 程文英;（n，κ）-星图的条件边容错哈密尔顿性[D];湖北大学;2013年

2 蔡红艳;泡型星图的局部连通性及匹配排除[D];湖北大学;2013年

3 张娟;两类网络有关条件边连通性的研究[D];中国科学技术大学;2014年

4 李佳傲;整数5-流及相关问题研究[D];中国科学技术大学;2014年

5 闫小艳;星图互连网络的最小边界和可靠性研究[D];西安电子科技大学;2014年

6 陈光永;某些图类的k-距离控制数与K-距离约束数[D];中国科学技术大学;2014年

7 喻雪荣;三角金字塔网的若干性质[D];浙江师范大学;2014年

8 王培艳;某些网络的容错性及条件容错性[D];北京交通大学;2014年

9 朱文慧;五类变换图的圈边连通性[D];湖北师范学院;2014年

10 李小燕;两类网络拓扑结构的可靠性评估[D];福建师范大学;2014年

，

本文编号：885050