圖的拉普拉斯譜的一些極值和排序問題.pdf

1、在圖論中，為了研究圖的性質(zhì)，人們引進(jìn)了各種各樣的矩陣，諸如圖的鄰接矩陣，關(guān)聯(lián)矩陣，距離矩陣，拉普拉斯矩陣等等，這些矩陣與圖都有著自然的聯(lián)系。代數(shù)圖論的一個(gè)主要問題就是研究圖的性質(zhì)能否以及如何由這些矩陣的代數(shù)性質(zhì)反映出來，這里所指的矩陣的代數(shù)性質(zhì)，主要指矩陣的特征值。 在上面所提到的矩陣中，最重要的有兩個(gè)：圖的拉普拉斯矩陣和鄰接矩陣。圖的拉普拉斯矩陣的特征值和鄰接矩陣的特征值都是圖的在同構(gòu)下的不變量，圖的鄰接矩陣及其特征值是代數(shù)圖

2、論的一個(gè)基本的研究課題。在過去的幾十年中，人們對圖的鄰接矩陣的特征值已經(jīng)進(jìn)行了大量的研究。和圖的鄰接矩陣相比，由于在拉普拉斯矩陣中含有圖的頂點(diǎn)度的信息，因此圖的拉普拉斯矩陣的特征值與圖的很多不變量之間有著更加密切的聯(lián)系。正如Mohar所說：圖的拉普拉斯矩陣的特征值更能反映它的圖論性質(zhì)。因此，對圖的拉普拉斯矩陣的特征值的研究越來越受到人們的廣泛關(guān)注。 本文主要研究圖的拉普拉斯特征值，具體分為如下三個(gè)方面：一是對圖的第二大拉普拉斯特

3、征值的研究；二是對圖的拉普拉斯譜半徑的研究；三是對圖的代數(shù)連通度的研究。 在第1章中，介紹了與圖和拉普拉斯矩陣有關(guān)的基本概念以及矩陣論中的一些基本定理。 在第2章中，研究了n階樹的第二大拉普拉斯特征值λ2(T)的最大值和排序問題。關(guān)于這一問題，當(dāng)n是偶數(shù)的情形，張曉東和李炯生在[102]中已經(jīng)解決了最大值的問題。但對n是奇數(shù)情形時(shí)的最大值問題卻一直沒有解決。本章中，我們確定了奇數(shù)階樹的第二大拉普拉斯特征值的最大與次大值：

4、即階為2t+1(t≥4)的樹T的第二大拉普拉斯特征值λ2(T)的最大值是1/2(t+1+√t2+2t-3)，次大值是方程x3-(2t+3)x2+(t2+3t+3)x-(2t+1)=0的第二大根；且進(jìn)一步找出了達(dá)到最大值的唯一的樹T1及達(dá)到次大值的唯一的樹T2。我們還研究了具有幾乎完美匹配的樹的第二大拉普拉斯特征值，給出了幾乎完美匹配樹的第二大拉普拉斯特征值的一個(gè)上界。 對圖的拉普拉斯特征值而言，最重要的兩個(gè)特征值是最大的拉普拉斯

5、特征值和第二小的拉普拉斯特征值，分別稱為圖的拉普拉斯譜半徑和代數(shù)連通度。最近，人們發(fā)現(xiàn)拉普拉斯譜半徑在理論化學(xué)上有重要的應(yīng)用見文獻(xiàn)；圖的代數(shù)連通度還可以被用來研究一些困難的圖論問題，例如：圖的擴(kuò)展性質(zhì)，等周數(shù)，最大割問題，以及圖的直徑等等。在第3章和第4章中，我們將分別討論圖的這兩個(gè)拉普拉斯特征值。 在第3章中，研究了樹的拉普拉斯譜半徑。關(guān)于這一問題，邵嘉裕，袁西英跟何常香在[116]中對具有完美匹配的樹按照拉普拉斯譜半徑進(jìn)行了

6、排序。但關(guān)于幾乎完美匹配樹的拉普拉斯譜半徑，只有郭繼明在[51]中，確定了幾乎完美匹配樹的拉普拉斯譜半徑的最大值，并且給出了相應(yīng)的極樹。我們在郭繼明已確定最大值的基礎(chǔ)上，進(jìn)一步確定了n階幾乎完美匹配樹的拉普拉斯譜半徑的第二到第六大的值，并且給出了達(dá)到這五個(gè)值的相應(yīng)的樹。 在第4章中，研究了圖的代數(shù)連通度。用T2k+1表示階為2k+1的具有幾乎完美匹配的樹的集合，α(T)表示樹T的代數(shù)連通度。我們確定了幾乎完美匹配樹的代數(shù)連通度的