單圈圖的擴(kuò)展能量的上界

徐幼專

邵陽廣播電視大學(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)的所有特征值的集合.

在文獻(xiàn)[12]中，Yang等引入了一個新的矩陣，稱為擴(kuò)展鄰接矩陣，用Aex(G)=(aij)表示，其中

因為Aex(G)是實對稱矩陣，它的特征值是實數(shù)，不妨設(shè)特征值為ηi(i=1,2,…,n),并且η1≥η2≥…≥ηn.

單圈圖就是邊數(shù)等于頂點數(shù)的簡單連通圖，單圈圖是除樹之外結(jié)構(gòu)最簡單的圖類，它在圖譜理論、復(fù)雜網(wǎng)絡(luò)、圖染色理論等都發(fā)揮著不可替代的作用.本文研究單圈圖的擴(kuò)展能量的上界問題.

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 具有5個頂點的單圈圖
Fig.1 Unicyclic graphs with 5 vertices