圖的最小特征根和拉普拉斯譜半徑.pdf

1、圖譜理論是圖論研究的一個非?；钴S而又重要的研究領域，它在量子化學、統(tǒng)計力學、計算機科學、通信網(wǎng)絡以及信息科學中均有著廣泛的應用。圖譜理論的研究主要是利用成熟的代數(shù)理論和技巧，并結合圖論和組合數(shù)學的理論來研究圖譜、圖的結構性質以及與圖的其它不變量（如色數(shù)、度序列、直徑、圍長、連通度等）之間的關系，它將圖與網(wǎng)絡的代數(shù)性質與其拓撲性質緊密地結合在一起。在圖譜理論中，為了研究圖的性質，人們引入了各種各樣的矩陣，諸如圖的鄰接矩陣、關聯(lián)矩陣、距離矩

2、陣、拉普拉斯矩陣等等，這些矩陣與圖的結構都有著密切的聯(lián)系。圖譜理論的一個主要問題就是研究圖的性質能否以及如何由這些矩陣的代數(shù)性質反映出來，這里所說的矩陣的代數(shù)性質，主要是指矩陣的特征值所刻畫的性質。在上面所提到的矩陣中，最重要的兩個就是圖的鄰接矩陣和圖的拉普拉斯矩陣。圖的鄰接矩陣的特征值和圖的拉普拉斯矩陣的特征值都是在圖的同構下的不變量．對圖的鄰接矩陣特征值而言，最重要的兩個特征值是最大特征值和最小特征值，分別稱為圖的譜半徑和最小根．對

3、圖的譜半徑的研究，文獻中存在大量的結果，已經(jīng)形成了比較完善的理論體系。而對最小根而言，研究的結果還很少。在圖的拉普拉斯特征值中，最重要的也有兩個：圖的最大拉普拉斯特征值（即拉普拉斯譜半徑）和圖的次小拉普拉斯特征值（即代數(shù)連通度）。本文主要圍繞圖的最小根和拉普拉斯譜半徑進行研究，首先介紹圖的最小根和拉普拉斯譜半徑的研究背景和進展，然后分四部分詳細地介紹我們圍繞這兩個課題所取得的主要研究成果。主要結果如下：
　　 ⑴在第二章中我們討

4、論直徑固定的一般圖。用(?)n，d表示直徑為d的n階連通圖的集合。對任意的圖G∈(?)n，d，通過考慮圖G的連通生成二部子圖的最小根，我們獲得了圖G的最小根的一個下界。進一步地，作為一個推論，給出了圖G的拉普拉斯譜半徑的一個上界。
　　 ⑵在第三章中我們研究圖的最小根與圖的不變量．用u（n，κ）表示懸掛點數(shù)為κ的n階單圈圖的集合．利用移接變形的技巧和特征多項式的一些技巧，刻畫了最小根達到最小的單圈圖。用B（n，k）表示懸掛點數(shù)為

5、κ的n階雙圈圖的集合。綜合利用圖譜理論的多種工具和手段，確定了最小根達到最小的雙圈圖．在本章的最后一節(jié)，我們考慮了圖的不變量直徑．用U（n，d）表示直徑為d的n階單圈圖的集合，結合圖的不變量直徑，我們刻畫了最小根達到最小的單圈圖。
　　 ⑶在第四章中我們討論三圈圖的譜。用Tn表示n階三圈圖的集合．對n〉52，我們確定了最小根取到最小的唯一的三圈圖。
　　 ⑷在第五章中我們討論樹的拉普拉斯譜半徑．用Tn,d表示直徑為d的n