本文關(guān)鍵詞：關(guān)于圖的獨立多項式的研究，由筆耕文化傳播整理發(fā)布。

【摘要】：圖G的獨立多項式I(G；x)=∑k=0α(G)sk·xk,表示基數(shù)為k的獨立集數(shù)目,其中k：∈{1…,a(G)},α(G)是圖G的極大獨立集的數(shù)目.在本文中我們探討?yīng)毩⒍囗検?(G；x)的一些重要性質(zhì),并得到以下結(jié)果：(1)對于樹或者是單圈圖,如果圖G是圍長g≥6(或者g≥5)和G≠qC7(或者G≠gK2)的良好覆蓋圖(非常良好覆蓋圖),其中g(shù)是任意正整數(shù),有,(G;-1)=0.即對于圖G,偶數(shù)階獨立集和奇數(shù)階獨立集的數(shù)目是相等的.(2)存在圖序列G1,G2,…,Gn,…,使得|I(Gn+1；-1)|-|(Gn+1;-1)|=2n,n=1,2,….也就是說存在圖序列,當(dāng)圈秩數(shù)增加1時,圖的偶數(shù)階獨立集與奇數(shù)階獨立集差的絕對值是以指數(shù)級增加的；另一方面,存在圖序列H1,H2,…,Hn,使得|I(Hn;-1)|≤M(M0),n=1,2,….即存在圖序列,當(dāng)圈秩數(shù)增加時,圖的偶數(shù)階獨立集與奇數(shù)階獨立集數(shù)值差不大于數(shù)M.(3)對于平面基圖G(沒有垂點),當(dāng)β(G)=2時,證明了|I(G;-1)|≤2β(G)-1.證明了Levit和Mandrescu提出的猜想：對任意滿足|q|≤2β的正整數(shù)β和整數(shù)q,存在連通圖G,有圈秩數(shù)β(G)=β和I(G；-1)=q.
【關(guān)鍵詞】：獨立集 圖的獨立多項式 有界性 單調(diào)性 良好覆蓋圖
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O174.14;O157.5
【目錄】：

• 中文摘要6-7
• 英文摘要7-11
• 第一章 前言11-22
• §1.1 引言11-13
• §1.2 圖的獨立多項式的基本性質(zhì)13-22
• 第二章 圖的構(gòu)造22-34
• §2.1 圈秩數(shù)β(G)≤2的圖的獨立多項式23-31
• §2.2 圈秩數(shù)β(G)≥3的圖的獨立多項式31-34
• 第三章 總結(jié)34-36
• §3.1 總結(jié)34-36
• 參考文獻36-38
• 致謝38

【相似文獻】

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

1 徐新萍;;獨立集的度和與圖的哈密爾頓性[J];運籌學(xué)學(xué)報;2006年03期

2 李國君，劉振宏;3－連通正則無爪圖的Hamilton圈[J];數(shù)學(xué)進展;1996年01期

3 林育青;關(guān)于簡單圖的獨立集多項式[J];東北重型機械學(xué)院學(xué)報;1997年02期

4 徐新萍;;哈密爾頓性和部分平方圖的獨立集(英文)[J];南京師大學(xué)報(自然科學(xué)版);2006年02期

5 趙樹峰;趙小玲;;樹圖的r-色獨立集劃分問題[J];漯河職業(yè)技術(shù)學(xué)院學(xué)報;2007年02期

6 崔麗麗;方奇志;孔亮;;獨立集對策的核心穩(wěn)定性[J];自然科學(xué)進展;2008年04期

7 江蓉;王守中;;一類三角系統(tǒng)的匹配數(shù)與點獨立集數(shù)[J];西南師范大學(xué)學(xué)報(自然科學(xué)版);2009年01期

8 徐新萍;;哈密爾頓性和部分平方圖的獨立集[J];數(shù)學(xué)的實踐與認識;2009年10期

9 王蒙;田雙亮;;若干圖的r-色獨立集劃分問題[J];西北民族大學(xué)學(xué)報(自然科學(xué)版);2011年02期

10 林翠琴，居余馬;獨立集上最小最大比值和最小極差比值問題的算法[J];清華大學(xué)學(xué)報(自然科學(xué)版);1994年06期

中國重要報紙全文數(shù)據(jù)庫 前2條

1 麻玉秀;獨立集采人：挖掘聚眾效應(yīng)下的財富[N];中國經(jīng)營報;2006年

2 本報記者　 張迪;獨立集采人組織家裝團購月入萬元[N];北京日報;2006年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前4條

1 張海良;關(guān)于圖的兩類多項式及相關(guān)指數(shù)的研究[D];華東師范大學(xué);2013年

2 徐新萍;圖的哈密爾頓性的若干結(jié)果[D];南京師范大學(xué);2003年

3 宋文兔;網(wǎng)絡(luò)分解在網(wǎng)絡(luò)編碼中的應(yīng)用[D];北京大學(xué);2012年

4 王世英;圖的匹配的若干結(jié)構(gòu)性問題[D];鄭州大學(xué);2000年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 何盼英;關(guān)于圖的獨立多項式的研究[D];華東師范大學(xué);2016年

2 景偉;幾類圖的匹配、點獨立集、點極大獨立集的計數(shù)[D];華中師范大學(xué);2009年

3 王華平;點獨立集度和的幾個結(jié)果[D];江西師范大學(xué);2002年

4 鄒玲平;格子系統(tǒng)的獨立集的計數(shù)[D];廈門大學(xué);2007年

5 朱志峰;一些圖的獨立多項式的單峰型性質(zhì)[D];大連理工大學(xué);2005年

6 徐敏;關(guān)于圖的Hamilton性的幾個新結(jié)果[D];南京師范大學(xué);2002年

7 王金杰;基于獨立集求解圖著色問題[D];華中科技大學(xué);2013年

8 續(xù)曉欣;Q0-1規(guī)劃模型下最大團、最大加權(quán)獨立集問題的研究[D];太原理工大學(xué);2006年

9 紀乃丹;圖的獨立集多項式和Clar覆蓋多項式的轉(zhuǎn)移矩陣計算[D];蘭州大學(xué);2006年

10 李樹花;關(guān)于κ-匹配和κ-獨立集的極值多聯(lián)苯鏈及一些和圖的點PI指標(biāo)[D];新疆師范大學(xué);2010年

  本文關(guān)鍵詞：關(guān)于圖的獨立多項式的研究，由筆耕文化傳播整理發(fā)布。

，

本文編號：378365