本文關(guān)鍵詞：幾類圖的弱飽和數(shù)的研究

  更多相關(guān)文章： 飽和圖 弱飽和數(shù) 多重圖 完全二部圖 完全圖 補(bǔ)圖

【摘要】：給定一個(gè)圖F,圖G是關(guān)于圖F的n階飽和圖,如果|V(G)|=n,并且在G中沒有與圖F同構(gòu)的子圖,但是對(duì)于圖G的補(bǔ)圖G中的任意邊e,在G+e中有一個(gè)與圖F同構(gòu)的子圖。用SAT(n,F)表示圖F的n階飽和圖的集合,集合SAT(n,F)中圖的最小邊數(shù)稱為飽和數(shù),記作sat(n,F)。圖G是關(guān)于圖F的n階弱飽和圖,如果|V(G)|=n,且在G中沒有與圖F同構(gòu)的子圖,但是對(duì)于圖G的補(bǔ)圖G中的所有邊存在一個(gè)排序,按這個(gè)排序在圖G上依次加G中所有邊,每次加一條邊,可以產(chǎn)生一個(gè)包含所加邊且與圖F同構(gòu)的子圖,持續(xù)這個(gè)過程,直到我們得到一個(gè)完全圖。用wSAT(n,F)表示圖F的n階弱飽和圖的集合,集合wSAT(n,F)中圖的最小邊數(shù)稱為弱飽和數(shù),記作wsat(n,F)。相比較已經(jīng)取得較完整理論體系的極圖理論的研究,圖的弱飽和數(shù)的研究還沒有得到比較好的一般性的結(jié)論。一種獲得圖弱飽和數(shù)一般性結(jié)論的方法是：研究幾類具體圖的弱飽和數(shù),確定這些圖達(dá)到弱飽和數(shù)時(shí)的性質(zhì),然后推廣到一般情況。本文主要研究了幾類圖的弱飽和數(shù),主要包括以下四部分：第一章介紹了圖G的飽和數(shù)與弱飽和數(shù)的概念,國(guó)內(nèi)外研究現(xiàn)狀,本文所用的重要符號(hào)及本文主要研究結(jié)果。第二章給出了wsat(n,Kt－K1,m),完全回答了[11]中的問題3：對(duì)于圖Kt－K1,m,2≤ mt－1, wsat(n,Kt－K1,m)=n(t－m－2)－t2－(2m+3)t/2－(m+1)是否成立。又給出了wsat(n,Kt－K2)和wsat(n,Kt－2K2),部分回答了[11]中的問題4：對(duì)于圖Kt－sK2,1≤ st－1/2, wsat(n,Kt－sK2)=(t－1/2)－s+(n－t+1)(t－3)是否成立。還推廣了[12]中方法,給出了wsat(n,k(K5－K2))、wsat(n,k(Kt－K2))和wsat(n,k(Kt－K1,m)),部分回答了[12]中的問題1：當(dāng)k≥2,n充分大時(shí),什么樣的連通圖G能夠滿足wsat(n,kG)=wsat(n,G)+k－1。第三章給出了wsat(n,kpUKq)(p≤q),這是對(duì)wsat(n,kKt)[12]的推廣。通過改進(jìn)[11]中方法,又給出了wsat(n,K2,6)和wsat(n,K2,t),部分回答了論文[11]中的問題2：對(duì)于最小度為δ的圖F,|V(F)|=p,|E(F)|=q,n≥p,當(dāng)圖F滿足什么性質(zhì)時(shí)才能使q-1+(δ-1)(n－p)≤wsat(n,F)≤(p－1/2)+(δ－1)(n－p+1)成立。第四章給出了wsat(n,K3,4)和wsat(n,Kt,t+1)的上界,部分回答了論文[11]中的問題2,并提出了一個(gè)公開問題。
【學(xué)位授予單位】：鄭州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 王殿軍;完全圖圈分解的一種新方法[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯(中文版);1993年04期

2 鄧覲超,佟玉鳳;有關(guān)完全圖的算法及實(shí)現(xiàn)技術(shù)[J];煙臺(tái)大學(xué)學(xué)報(bào)(自然科學(xué)與工程版);1997年03期

3 張文軍;;完全圖的最小6-圈覆蓋和8-圈覆蓋[J];山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年04期

4 O賜蜢，

本文編號(hào)：1278356