連通圖的譜半徑和圖的拉譜拉斯譜半徑的估計(jì).pdf

1、設(shè)圖G=(V，E)是具有n頂點(diǎn)和m條邊的簡單連通圖，圖G的鄰接矩陣A=A(G)=(αuv)n×n，其中αuv表示頂點(diǎn)u和v鄰接，圖G的鄰接矩陣A(G)的特征值μ1≥μ2…≥μn，其中μ1為鄰接矩陣A(G)的最大特征值，稱為圖G的鄰接矩陣的譜半徑，簡記為ρ(G)．D=D(G)=diag{d1，d2，…，dn}為圖G的度對角矩陣，則圖G的Laplacian矩陣定義為L(G)=D(G)—A(G)．已知L(G)是實(shí)對稱半正定的奇異M矩陣，故特征

2、值均是非負(fù)的．又L(G)的行和均為0，故0是最小特征值，因此可假定L(G)的特征值為λ1(G)≥λ2(G)≥…≥λn-1(G)≥λn(G)=0，其中λ1(G)為圖G的Laplacian矩陣特征值的最大值，稱為圖G的Laplacian譜半徑，簡記為λL(G)．設(shè)K(G)=D(G)+A(G)，稱為圖G的擬—Laplacian矩陣，其中它為非負(fù)不可約的實(shí)對稱矩陣，它的特征值非負(fù)．連通圖G的譜半徑和圖G的Laplacian矩陣的譜半徑具有重要的

3、圖論和實(shí)際意義，因?yàn)樗鼈兣c圖論的不變量有著緊密聯(lián)系，在實(shí)際生產(chǎn)中，對于連通圖的譜半徑和圖的Laplacian的譜半徑的估計(jì)很重要．故本文對于ρ(G)和λL(G)的估計(jì)做以下的工作． (1)利用代數(shù)的方法和非負(fù)矩陣?yán)碚摰贸鲞B通圖的ρ(G)上界和達(dá)到上界的圖，并且用圖例說明這一些新結(jié)果對于以前的一些結(jié)果有很好的改進(jìn)． (2)在度序列和邊數(shù)的條件下，利用重要不等式的方法得到與相似矩陣B有相同的特征值，λL(G)上界估計(jì)和達(dá)到上