幾類笛卡爾積圖的H-強(qiáng)迫集和H-強(qiáng)迫數(shù).pdf

1、在圖論中，與圈相關(guān)的問題一直是圖論學(xué)者研究的重點之一.近年來，有關(guān)于哈密爾頓圈的問題更是受到大量科研工作者的廣泛關(guān)注，而隨著圖論學(xué)者I.Fabrici, E.Hexel和 S.Jendrol提出哈密爾頓圖的H-強(qiáng)迫集和H-強(qiáng)迫數(shù)的概念后，有關(guān)于哈密爾頓圖的 H-強(qiáng)迫集和H-強(qiáng)迫數(shù)問題也成為了學(xué)者們研究的熱點。本文主要研宄某些笛卡爾積圖的H-強(qiáng)迫集和H-強(qiáng)迫數(shù)。研究這些圖的H-強(qiáng)迫集和H-強(qiáng)迫數(shù)，一方面將加深我們對這些哈密爾頓圖的結(jié)構(gòu)認(rèn)識

2、，另一方面將有助于改進(jìn)在這些圖類中尋找哈密爾頓圈的算法。除此之外，探討了強(qiáng)連通的圓的局部競賽圖的哈密爾頓分解問題。
　　本研究分為四個部分：第一章，緒論.介紹了研宄背景和基本概念。第二章，在無向圖中，討論了圈和路的笛卡爾積圖的H-強(qiáng)迫集和H-強(qiáng)迫數(shù)。由笛卡爾積的定義，得到了圈和路作笛卡爾積后的圖，并以此研宄了所得圖的 H-強(qiáng)迫集與H-強(qiáng)迫數(shù)，利用尋找非哈密爾頓圈的方法證明了主要結(jié)論：設(shè)圖G= Ck×Pl,其中k≥2, l≥1.則有

3、(i)當(dāng) k=2時，h(G)=2.(ii)當(dāng) k≥3時，此處公式省略。第三章，在有向圖中，討論有向圈和有向路的笛卡爾積圖的H-強(qiáng)迫集和H-強(qiáng)迫數(shù).并通過證明得到如下結(jié)論：設(shè)（→Cn）和（→Ckn）是兩個有向圈，其中n為正整數(shù)且n≥2, k=1,2,3,???,則(i)有向圖（→Cn）×（→Ckn）為哈密爾頓圖.(ii) h（→Cn）×（→Ckn）= k n,并且H-強(qiáng)迫集為此處公式省略。第四章，研宄了強(qiáng)連通的圓的局部競賽圖的哈密爾頓分解