徐幼專

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

設(shè)G是一個(gè)簡(jiǎn)單圖，頂點(diǎn)集為V(G)={v1,v2,…,vn}.用di表示頂點(diǎn)vi的度，同時(shí), 分別用Δ、δ表示G中的最大度和最小度.G的鄰接矩陣用A(G)表示,設(shè)A(G)的特征值為λi(i=1,2,…,n).因?yàn)锳(G)是一個(gè)實(shí)對(duì)稱矩陣，它的所有特征值都是實(shí)數(shù)，不妨設(shè)λ1≥λ2≥…≥λn，G的譜是鄰接矩陣A(G)的所有特征值的集合.

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

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

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

1 主要引理

為了證明本文的定理，需要引入下列幾個(gè)引理.

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

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

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

(1)若2m≥n，則

(2)若2m≤n，則E(G)≤2m，等式成立當(dāng)且僅當(dāng)G是邊不相交的并或?yàn)楣铝㈨旤c(diǎn).

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

2 主要結(jié)論

現(xiàn)在，我們利用最大度、最小度來(lái)證明本文的結(jié)論.

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

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