單圈圖的擴(kuò)展矩陣的譜半徑與能量

徐幼專

(邵陽(yáng)廣播電視大學(xué)，湖南 邵陽(yáng)，422000)

能量的概念起源于化學(xué)，20世紀(jì)30年代，Huckel 分子軌道理論提出了一種對(duì)共軛烴的薛定諤方程求近似解的方法，這一方法，可以用來(lái)估計(jì)共軛烴中π-電子的分子軌道能級(jí)，并計(jì)算π-電子的總能量。圖的特征值和共軛碳?xì)浠衔镏笑?電子的分子軌道能級(jí)之間有著緊密對(duì)應(yīng)，碳?xì)浠衔锵到y(tǒng)的碳原子對(duì)應(yīng)于相關(guān)分子圖的頂點(diǎn)，分子圖的能量定義為其鄰接矩陣的特征值的絕對(duì)值之和。圖的能量是圖的一個(gè)不變量，對(duì)于圖的能量研究有許多結(jié)果，參見文獻(xiàn)[1-4]。能量的概念有很多推廣，至今為止，已有63種能量得到研究[5]。

這篇文章主要研究單圈圖的擴(kuò)展譜半徑和擴(kuò)展能量。

1 預(yù)備知識(shí)

設(shè)G是具有n個(gè)頂點(diǎn)的簡(jiǎn)單圖，其頂點(diǎn)集為V(G)={v1，v2，…，vn}，邊集為E(G)，令|E(G)|=m。用di表示頂點(diǎn)vi的度，同時(shí)，用Δ、δ分別表示G中的最大度和最小度。若頂點(diǎn)vi與vj相鄰，則記作vivj∈E(G)。圖G的鄰接矩陣用A(G) 表示，設(shè)A(G)的特征值為λi(i=1，2，…，n)，不妨設(shè)λ1≥λ2≥…≥λn，這個(gè)最大的特征值λ1稱為圖G的譜半徑。因?yàn)锳(G)是一個(gè)實(shí)對(duì)稱矩陣，它的所有特征值都是實(shí)數(shù)。圖G的譜是指其鄰接矩陣A(G)的所有特征值的集合。單圈圖就是邊數(shù)等于頂點(diǎn)數(shù)的簡(jiǎn)單連通圖，單圈圖是除樹之外結(jié)構(gòu)最簡(jiǎn)單的圖類，它在圖譜理論、復(fù)雜網(wǎng)絡(luò)、圖染色理論等都發(fā)揮著不可替代的作用。

圖的擴(kuò)展鄰接矩陣被YANG介紹過(guò)[6]，定義圖的擴(kuò)展鄰接矩陣Aex=(aexij)，這里

1)設(shè)G是頂點(diǎn)數(shù)為n、邊數(shù)為m的簡(jiǎn)單圖，則

(1)

等式成立當(dāng)且僅當(dāng)G≌K1，n-1，這里K1，n-1表示具有n個(gè)頂點(diǎn)的星圖。

2)設(shè)G是最大度為Δ、最小度為δ的簡(jiǎn)單圖，則

(2)

等式成立當(dāng)且僅當(dāng)G是正則圖，這里λ1為圖G的鄰接譜半徑。

設(shè)G是頂點(diǎn)數(shù)為n、邊數(shù)為m、最大度為Δ、最小度為δ的簡(jiǎn)單圖，則

(3)

(4)

2 定理及其證明

先介紹幾個(gè)引理。

下面證明文中的主要結(jié)論。

定理1 設(shè)G是頂點(diǎn)數(shù)為n的單圈圖，則G的擴(kuò)展譜半徑滿足

圖1 具有5個(gè)頂點(diǎn)的單圈圖S35Fig.1 Unicyclic graph S35 with 5 vertices

證明 因?yàn)镚是頂點(diǎn)數(shù)為n的單圈圖，所以其邊數(shù)m=n。代入(1)式即得結(jié)論。

例如，以單圈圖S35為例(見圖1)，計(jì)算它的擴(kuò)展譜半徑。利用mathematica軟件直接計(jì)算單圈圖的擴(kuò)展矩陣的特征值譜為{4.25，0，0，0，-4.25}，得到擴(kuò)展譜半徑為η1=4.25。 若利用定理1求得η1≤5.205。顯然，η1=4.25<5.205，定理1成立。

定理2 設(shè)G是頂點(diǎn)數(shù)為n、最大度為Δ、最小度為δ的單圈圖，則G的擴(kuò)展譜半徑滿足

證明 分兩種情形給予討論

(5)

情形2 若單圈圖的最小度δ>1，根據(jù)引理1和(2)式，得到

(6)

于是推出定理的結(jié)論。

再以單圈圖S35為例，因?yàn)槠渥畲蠖圈?4，若用(5)式計(jì)算，則η1≤13.47。顯然，η1=4.25<13.47，定理2是成立的。

定理3 設(shè)G是n(n≥9)階、最大度為Δ、最小度為δ的單圈圖，則G的擴(kuò)展譜半徑滿足

同定理2證明一樣，利用引理2，馬上得出結(jié)論，這里略去證明。

比較定理1、2、3，發(fā)現(xiàn)定理1的結(jié)果要優(yōu)于定理2、3的結(jié)果，定理3要優(yōu)于定理2。

下面，研究單圈圖的擴(kuò)展能量。

定理4 設(shè)G是頂點(diǎn)數(shù)為n、最大度為Δ、最小度為δ的單圈圖，則擴(kuò)展能量滿足

證明 對(duì)于單圈圖G，其邊數(shù)m與頂點(diǎn)數(shù)n相等，即m=n。

現(xiàn)分兩種情形討論：

于是，定理得到證明。

仍以單圈圖S35為例說(shuō)明定理4 的準(zhǔn)確性。由于單圈圖S35的擴(kuò)展譜為{4.25，0，0，0，-4.25}，因而求得S35的擴(kuò)展能量為Eex(S35)=8.5。因?yàn)棣?4，δ=1，若用定理4計(jì)算，則Eex(S35)≤15.03。顯然有8.5<15.03成立。

定理5 設(shè)G是頂點(diǎn)數(shù)為n、最大度為Δ、最小度為δ的單圈圖，r表示當(dāng)δ=1時(shí)的個(gè)數(shù)。則擴(kuò)展能量滿足

證明 對(duì)于單圈圖G，若δ=1，不妨設(shè)d1=d2=…=dr=1，dr+1>1，dr+2>1，…，dn>1。

若δ>1，則有F(G)≤nΔ3。所以有

從而定理得到證明。

繼續(xù)以單圈圖S35為例，驗(yàn)證定理5 的準(zhǔn)確性。由于單圈圖S35的最大度為4，最小度為1的有2個(gè)，因此有Eex(S35)≤45.40，顯然定理5成立。

從上發(fā)現(xiàn)用定理4估計(jì)，比用定理5去估計(jì)結(jié)果更準(zhǔn)確一些。