k元n方體和OTG圖的H-強(qiáng)迫數(shù).pdf

1、在圖理論中，哈密爾頓圈問(wèn)題一直是人們重點(diǎn)關(guān)注的問(wèn)題。G的一個(gè)圈稱(chēng)為哈密爾頓圈，如果它包含G中所有點(diǎn).圖G稱(chēng)為一個(gè)哈密爾頓圖如果它包含一個(gè)哈密爾頓圈。若G是一個(gè)哈密爾頓圖，對(duì)于非空頂點(diǎn)集X c V(G),如果每個(gè)包含X的圈都是哈密爾頓圈，則X稱(chēng)為G的 H-強(qiáng)迫集.最小的H-強(qiáng)迫集的頂點(diǎn)個(gè)數(shù)稱(chēng)為G的H-強(qiáng)迫數(shù)。H-強(qiáng)迫數(shù)和H-強(qiáng)迫集這兩個(gè)概念是由I。Fabrici等人在2009年提出的概念.因?yàn)檫@個(gè)概念對(duì)于研宄圖的哈密爾頓性有重要意義，所以

2、這一概念一經(jīng)提出就引起了人們的廣泛關(guān)注。k元n方體，是一種特殊的拓?fù)渚W(wǎng)絡(luò)模型，記為 Qkt(k≥1, n≥1).它有 kn個(gè)頂點(diǎn),每個(gè)頂點(diǎn)可以記為u= Un-l Un-2...U0,其中 Ui∈{0,1,…k-1},0≤i≤ n-1.頂點(diǎn)U= Un-lUn-2…U0和頂點(diǎn)V= Vn-lVn-2…Vo相鄰當(dāng)且僅當(dāng)存在一個(gè)整數(shù)j,0≤j≤ n-1,使得Uj= Vj士1(mod k)且對(duì)每個(gè) i∈{0,1,...,j-1,j+1,...,n-

3、1}都有 Ui= Vi.對(duì)于 G中每一對(duì)不相鄰的頂點(diǎn)u,V,如果d(U)+d(V)≥ n,則稱(chēng) G滿足了 Ore定理的條件.為了方便，用 OTG表示一個(gè)滿足Ore定理?xiàng)l件的圖。Ore證明了任意一個(gè)OTG都是哈密爾頓圖.本文研究的是網(wǎng)絡(luò)拓?fù)鋱Dk元n方體Qkt和OTG圖的H-強(qiáng)迫集和H-強(qiáng)迫數(shù),通過(guò)分析圖形結(jié)構(gòu)及分類(lèi)歸納來(lái)得到結(jié)論。
　　本研究分為四個(gè)部分：第一章是緒論,介紹了本文的研究背景及相關(guān)結(jié)論。第二章是基本概念,介紹了本文將要

4、用到的術(shù)語(yǔ)和概念。第三章通過(guò)研究Cm×Cn的H-強(qiáng)迫數(shù),得出網(wǎng)絡(luò)拓?fù)鋱Dk元n方體Qkn的H-強(qiáng)迫數(shù).分別得到三個(gè)主要的結(jié)論：設(shè) G= Cm×Cn(m>2, n>2),則此處公式省略；設(shè) G= Qkn(n≥2, k>2),則此處公式省略；設(shè)G= Pn×Pn(n≥4,且 n為偶數(shù))，則 h(G)= n2/2—2。第四章研究了OTG圖的H-強(qiáng)迫數(shù)和最小H-強(qiáng)迫集.通過(guò)研究這類(lèi)圖的弱閉包得到這一類(lèi)圖的H-強(qiáng)迫數(shù)為n或n-2或 n/2,并由此給出