圖的最大拉普拉斯特征值.pdf

1、設(shè)G是n階簡單連通圖，H是圖G的線圖，D和A分別為G的頂點(diǎn)度對角矩陣和鄰接矩陣，DH和B分別為H的度對角矩陣和鄰接矩陣，U=diag(dudv:uv∈E(G))是一對角矩陣。則L=D-A稱為G的拉普拉斯(Laplace)矩陣，而K=D+A稱為擬拉普拉斯矩陣。研究圖的Laplace矩陣的特征值有著重要的圖論意義和實際意義，因為它與圖的許多不變量有著密切聯(lián)系。在許多應(yīng)用中，往往需要Laplace矩陣最大特征值λ1(G)的好的上界估計值。本文

2、針對λ1(G)的上界估計問題做了以下工作： 1.綜述了近年來有關(guān)λ1(G)的上界估計的主要結(jié)果，并作了全面比較分析。 2.將非負(fù)矩陣?yán)碚搼?yīng)用到相似變換矩陣D-1/2KD1/2，DH-1/2BDH1/2和U-1/2BU1/2并結(jié)合圖論性質(zhì)獲得了λ1(G)的幾個用頂點(diǎn)度數(shù)和頂點(diǎn)平均二次度表示的新的緊的上界。并確定了等式成立的全部極圖。同時幾個例子用于說明這些新的結(jié)果是不可比較的，并在一定意義上改進(jìn)了現(xiàn)有的大多數(shù)結(jié)果。

3、 3.將特征值與特征向量的關(guān)系應(yīng)用到線圖的鄰接矩陣B并利用不等式方縮技巧和圖的性質(zhì)獲得了λ1(G)的一個用圖的度序列，邊數(shù)表示的緊的上界估計式，并確定了相應(yīng)的極圖，同時舉例說明在一定情況下該估計值在同類結(jié)果中最優(yōu)。 4.利用矩陣分拆技巧將L分拆為兩個矩陣和的形式并利用著名的Weyl定理給出了一類具有割點(diǎn)、割邊圖的Laplace譜半徑的幾個上界估計式。這些估計式將高階圖類的Laplace譜半徑用較低階的子圖的Laplace譜半徑來