本文關(guān)鍵詞：圖的積和譜刻畫問題研究

  更多相關(guān)文章： 積和式 積和多項式 積和譜 積和零度 積和同譜圖 Gutman問題 特征多項式 鄰接譜

【摘要】：圖G的積和多項式由Merris等和Kasum等分別在數(shù)學(xué)和化學(xué)中幾乎同時引入,它通過矩陣xI-A(G)的積和式(permanent)來定義,其中I和A(G)分別是單位矩陣和G的鄰接矩陣.但Valiant證明了矩陣的積和式的計算是個轷P-完全問題.刻畫哪些圖類由其譜唯一確定是圖譜理論中一個經(jīng)典問題.van Dam和Haemers系統(tǒng)地研究了該問題,并猜想幾乎所有的圖都是鄰接譜確定的.圖的積和多項式的所有根(包含其重數(shù))構(gòu)成的重集稱為圖的積和譜Merris等首次提出了積和譜刻畫問題,即什么樣的圖是積和譜確定的?圖G是積和譜確定的是指任意與G有相同積和譜的圖H,必有H同構(gòu)于G.此外,他們認為除樹外圖的積和譜區(qū)分圖比鄰接譜要好一些.最近,柳順義和張和平開始探討了一些圖類是否是積和譜確定的,證明了星圖、完全圖、完全正則二部圖和奇圈是積和譜確定的.結(jié)果表明鄰接譜確定的圖不一定是積和譜確定的.兩個圖是積和同譜的是指它們有相同的積和譜.Borowiecki和Jozwiak最早考慮了積和同譜圖的構(gòu)造問題,主要探討了哪些圖對既是積和同譜的又是鄰接同譜的.本文中,我們對圖的積和譜刻畫問題做了系統(tǒng)的研究.證明了完全圖刪一些邊所得子圖是積和譜確定的.特別地,我們引入了圖的積和零度的概念,即,圖的積和譜中零根的數(shù)目.利用圖的積和零度參數(shù),證明了具有極值積和零度的圖是積和譜確定的,并證明了完全二部圖是積和譜確定的.此外,借助圖的積和零度和其匹配數(shù)之間的關(guān)系,證明了平衡完全二部圖刪一些邊所得子圖是積和譜確定的.最后,我們給出了一些構(gòu)造圖對既是積和同譜又是鄰接同譜的方法.第一章介紹了圖的積和多項式的研究背景.綜述了圖的積和多項式和積和譜的研究進展.第二章中我們以Merris等的看法為出發(fā)點探討了哪些完全圖刪除一些特殊邊所得的子圖是積和譜確定的.證明了完全圖至多刪除五條邊的所有子圖都是積和譜確定的.而Camara和Haemers的結(jié)果表明這類圖中恰有一對不能由鄰接譜所確定.此外,還證明了完全圖刪一個星,一個匹配以及一個匹配和路P3的不交并的邊所得的子圖是積和譜確定的.第三章進一步證明了完全圖刪除六條邊的所有子圖是積和譜確定的,并考慮了鄰接譜刻畫問題.發(fā)現(xiàn)了任意圖中長為4的閉途徑與其積和多項式第四個系數(shù)之間的關(guān)系,并借助于該關(guān)系拓展了Camara和Haemers的結(jié)果,證明了完全圖刪六條邊的所有子圖中僅有兩對鄰接同譜圖,即K5-E(K4)和K5-E(B),Kn-E(C6)和Kn-E(T2,2,2)分別是鄰接同譜的,其中B是一個領(lǐng)結(jié)圖,n≥7.第四章引入了圖的積和零度的概念,并給出了它的一些基本性質(zhì).進而完全刻畫了積和零度為n-2,n-3,n-4和n-5的圖,其中n為圖的頂點數(shù).這些圖恰好是僅有3,4,5或6個不同積和根的部分圖類.利用積和零度參數(shù),證明了積和零度為n-2,n-3,或n-5的圖以及積和零度為n-4的非二部圖是積和譜確定的.特別地,證明了完全二部圖是積和譜確定的.第五章借助圖的積和零度和匹配數(shù)之間的關(guān)系,證明了從平衡完全二部圖Kp,p中刪除一個星K1,l(lp)的邊所得子圖是積和譜確定的.此外,還證明了Kp,p刪至多五條邊的所有子圖中滿足其匹配數(shù)等于p的圖是積和譜確定的.在第六章中我們探討了哪些圖對既是積和同譜的又是鄰接同譜的.給出了一個構(gòu)造方法,得到了無數(shù)對森林是這樣的圖.此外,借助圖的粘接運算,可構(gòu)造了無窮多對圖是積和同譜的又是鄰接同譜的.最后,我們證明了圖G的積和多項式的導(dǎo)數(shù)等于其所有刪一個頂點的子圖的積和多項式之和.特別地,我們討論并解決了關(guān)于圖的積和多項式的Gutman問題.
【關(guān)鍵詞】：積和式 積和多項式 積和譜 積和零度 積和同譜圖 Gutman問題 特征多項式 鄰接譜
【學(xué)位授予單位】：蘭州大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 中文摘要3-5
• 英文摘要5-10
• 第一章 引言10-26
• 1.1 基本概念10-12
• 1.2 圖的積和多項式的研究背景12-15
• 1.3 圖的積和多項式和積和譜的研究進展15-24
• 1.4 本文的主要研究結(jié)果24-26
• 第二章 完全圖刪除一些邊所得子圖的積和譜刻畫26-40
• 2.1 準(zhǔn)備知識26-29
• 2.2 完全圖刪除至多五條邊所得子圖的積和譜刻畫29-37
• 2.2.1 兩個重要引理31-34
• 2.2.2 主要結(jié)果34-37
• 2.3 完全圖刪除特殊邊結(jié)構(gòu)所得子圖的積和譜刻畫37-40
• 第三章 完全圖刪六條邊子圖的積和譜和鄰接譜刻畫40-62
• 3.1 明定理3.140-53
• 3.1.1 準(zhǔn)備知識40-47
• 3.1.2 定理3.1的證明47-53
• 3.2 明定理3.253-60
• 3.2.1 一些引理53-55
• 3.2.2 定理3.2的證明55-60
• 3.3 結(jié)束語60-62
• 第四章 圖的積和零度與具有極值積和零度圖的積和譜刻畫62-76
• 4.1 圖的積和零度的一些基本性質(zhì)62-64
• 4.2 刻畫具有極值積和零度的圖64-68
• 4.3 具有積和零度的圖的積和譜刻畫68-74
• 4.3.1 積和零度為n-2和n-3的圖是積和譜確定的69
• 4.3.2 積和零度為n-4的非二部圖是積和譜確定的69-72
• 4.3.3 積和零度為n-5的圖是積和譜確定的72-74
• 4.4 完全二部圖的積和譜刻畫74
• 4.5 結(jié)束語74-76
• 第五章 平衡完全二部圖刪一些邊所得子圖的積和譜刻畫76-92
• 5.1 平衡完全二部圖刪星所得子圖是積和譜確定的76-78
• 5.2 平衡完全二部圖刪至多五條邊的子圖是積和譜確定的78-90
• 5.2.1 預(yù)備知識78-84
• 5.2.2 主要結(jié)果84-88
• 5.2.3 小結(jié)88-90
• 5.3 結(jié)束語90-92
• 第六章 積和同譜圖與圖積和多項式的Gutman問題92-102
• 6.1 構(gòu)造既是積和同譜又是鄰接同譜的圖對92-97
• 6.1.1 一個構(gòu)造方法92-95
• 6.1.2 粘接法的一個注記95-97
• 6.1.3 小結(jié)97
• 6.2 圖積和多項式的Gutman問題97-102
• 6.2.1 圖積和多項式的導(dǎo)數(shù)98-100
• 6.2.2 主要結(jié)果100-102
• 參考文獻102-110
• 在學(xué)期間的研究成果110-112
• 致謝112

【相似文獻】

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

1 張鐘嵊;利用對消法直接求網(wǎng)絡(luò)圖的樹積和及副樹積和[J];山東工業(yè)大學(xué)學(xué)報;1996年03期

2 彭求實;;一個關(guān)于積和的等式證明及其應(yīng)用[J];哈爾濱商業(yè)大學(xué)學(xué)報(自然科學(xué)版);2008年03期

3 焦?fàn)庿Q;王志更;;廣義L-R Smash-積和L-R Smash-余積[J];河南師范大學(xué)學(xué)報(自然科學(xué)版);2008年01期

4 馮良貴,郝志峰;亞投射環(huán)的積和矩陣擴張(英文)[J];數(shù)學(xué)進展;2001年02期

5 李金其,許永華;辮子monoidal范疇中的Smash余積和辮子群[J];中國科學(xué)(A輯 數(shù)學(xué) 物理學(xué) 天文學(xué) 技術(shù)科學(xué));1997年06期

6 郭艷蘋;;正確使用積和商的定位公式是提高珠算技術(shù)水平的重要途徑[J];北京農(nóng)業(yè)工程大學(xué)社會科學(xué)學(xué)報;1994年Z2期

7 傅建民;一個不等式的加細[J];黔東南民族師專學(xué)報;1994年Z1期

8 宋善炎;紀(jì)風(fēng)霞;;競賽專題八 物體的性質(zhì)[J];湖南中學(xué)物理;2010年09期

9 ;[J];;年期

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

1 吳廷增;圖的積和譜刻畫問題研究[D];蘭州大學(xué);2015年

2 柳順義;關(guān)于圖的積和多項式若干問題的研究[D];蘭州大學(xué);2013年

3 李巍;圖的積和多項式及其相關(guān)問題[D];蘭州大學(xué);2012年

，

本文編號：897215