雙圈圖的擴展能量的上界

周后卿

(邵陽學(xué)院 理學(xué)院，湖南 邵陽，422000)

設(shè)G是一個簡單圖，頂點集為V(G)={v1,v2,…,vn}。用di表示頂點vi的度，同時,分別用Δ、δ表示G中的最大度和最小度。G的鄰接矩陣用A(G) 表示,設(shè)A(G)的特征值為λi(i=1,2,…,n)。 因為A(G)是一個實對稱矩陣，它的所有特征值都是實數(shù)，不妨設(shè)λ1≥λ2≥…≥λn，G的譜是鄰接矩陣A(G)的所有特征值的集合。若G是一個具有頂點n的簡單連通圖，其邊數(shù)為n+1，則稱G為雙圈圖。

這篇文章將研究雙圈圖的擴展能量的上界問題。

1 幾個引理

為了證明這篇文章的定理，需要下列幾個引理。

引理1[13]設(shè)G是一個具有n個頂點的簡單圖，則

引理2[15]設(shè)G是一個具有n個頂點m條邊，度序列為d1,d2,…,dn的簡單圖,則

引理3[16]設(shè)G是一個具有n個頂點m條邊的簡單圖，

1)若2m≥n，則

2)若2m≤n，則E(G)≤2m，等式成立當(dāng)且僅當(dāng)G是邊不相交的并或為孤立頂點。

引理4[17]設(shè)G是一個具有n個頂點的簡單圖，則

2 主要結(jié)論

現(xiàn)在，利用最大度、最小度來證明下面的結(jié)論。

定理1 設(shè)G是一個具有n個頂點的雙圈圖，則

因此，對于雙圈圖來說，若δ=1，則由引理1有

以如下的圖1 為例，計算它的擴展能量。

圖1 具有7個頂點的雙圈圖G Fig.1 Bicyclic graph Gwith 7 vertices

利用mathematica軟件直接計算雙圈圖的特征值譜為{2.8558,1,0.3216,0,-1,-1,-2.1774}，得到雙圈圖的擴展矩陣的特征值譜是{5.6999,1,0.6263,0,-1,-1,-5.3262}，因此可算出擴展能量為Eex(G)=14.6524。 若利用定理1求，由于圖G的最大度為6，最小度為1，因此有

定理2 設(shè)G是一個具有n個頂點的雙圈圖，則

又因為G是雙圈圖，所以m=n+1。

再以圖1中的雙圈圖為例，利用定理2計算，得到Eex(G)≤99，定理是成立的。

證明 因為G是雙圈圖，于是有m=n+1，根據(jù)引理3，

仍以圖1中的雙圈圖為例，利用定理3計算，得到Eex(G)≤64.2857，定理成立。從上面的例子可看出，定理3的結(jié)果似乎比另外2個要精確一些。