论文部分内容阅读
在图理论中,哈密尔顿圈问题一直是人们重点关注的问题。G的一个圈称为哈密尔顿圈,如果它包含G中所有点.图G称为一个哈密尔顿图如果它包含一个哈密尔顿圈。若G是一个哈密尔顿图,对于非空顶点集X c V(G),如果每个包含X的圈都是哈密尔顿圈,则X称为G的 H-强迫集.最小的H-强迫集的顶点个数称为G的H-强迫数。H-强迫数和H-强迫集这两个概念是由I。Fabrici等人在2009年提出的概念.因为这个概念对于研宄图的哈密尔顿性有重要意义,所以这一概念一经提出就引起了人们的广泛关注。k元n方体,是一种特殊的拓扑网络模型,记为 Qkt(k≥1, n≥1).它有 kn个顶点,每个顶点可以记为u= Un-l Un-2...U0,其中 Ui∈{0,1,…k-1},0≤i≤ n-1.顶点U= Un-lUn-2…U0和顶点V= Vn-lVn-2…Vo相邻当且仅当存在一个整数j,0≤j≤ n-1,使得Uj= Vj士1(mod k)且对每个 i∈{0,1,...,j-1,j+1,...,n-1}都有 Ui= Vi.对于 G中每一对不相邻的顶点u,V,如果d(U)+d(V)≥ n,则称 G满足了 Ore定理的条件.为了方便,用 OTG表示一个满足Ore定理条件的图。Ore证明了任意一个OTG都是哈密尔顿图.本文研究的是网络拓扑图k元n方体Qkt和OTG图的H-强迫集和H-强迫数,通过分析图形结构及分类归纳来得到结论。 本研究分为四个部分:第一章是绪论,介绍了本文的研究背景及相关结论。第二章是基本概念,介绍了本文将要用到的术语和概念。第三章通过研究Cm×Cn的H-强迫数,得出网络拓扑图k元n方体Qkn的H-强迫数.分别得到三个主要的结论:设 G= Cm×Cn(m>2, n>2),则此处公式省略;设 G= Qkn(n≥2, k>2),则此处公式省略;设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-强迫集.令 Cw(G)是G的弱闭包, S是Cw(G)的最大独立集。则:H-强迫数 h(G)= n-2或 n/2或n;处公式省略其中x,y∈V(G)且 dcw(G)(x)=n-1, dCw(G)(y)= n-1。