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

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

2、這一概念一經(jīng)提出就引起了人們的廣泛關(guān)注。k元n方體，是一種特殊的拓撲網(wǎng)絡(luò)模型，記為 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相鄰當(dāng)且僅當(dāng)存在一個整數(shù)j,0≤j≤ n-1,使得Uj= Vj士1(mod k)且對每個 i∈{0,1,...,j-1,j+1,...,n-

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

4、用到的術(shù)語和概念。第三章通過研究Cm×Cn的H-強迫數(shù),得出網(wǎng)絡(luò)拓撲圖k元n方體Qkn的H-強迫數(shù).分別得到三個主要的結(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-強迫數(shù)和最小H-強迫集.通過研究這類圖的弱閉包得到這一類圖的H-強迫數(shù)為n或n-2或 n/2,并由此給出