徐幼專(zhuān)

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

若G是一個(gè)具有n個(gè)頂點(diǎn)和m條邊的簡(jiǎn)單連通圖，則

(1)

等式成立當(dāng)且僅當(dāng)G是一個(gè)正則圖;

(2)

等式成立當(dāng)且僅當(dāng)G是一個(gè)空?qǐng)D或是一條邊加n-2個(gè)孤立點(diǎn)所構(gòu)成的圖.

K C Das等[12]證明了如下結(jié)論：設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)、m條邊和秩為r的簡(jiǎn)單連通圖，則

稱(chēng)一個(gè)圖為循環(huán)圖，若它的鄰接矩陣是一個(gè)循環(huán)矩陣，即它是循環(huán)群上的Cayley圖.循環(huán)圖是一類(lèi)重要的互聯(lián)網(wǎng)絡(luò)拓?fù)鋱D，循環(huán)網(wǎng)絡(luò)是雙環(huán)網(wǎng)的自然推廣.循環(huán)圖具有較好的穩(wěn)定性、高對(duì)稱(chēng)性和可擴(kuò)展性，在過(guò)去的幾十年里，循環(huán)圖不斷地出現(xiàn)在編碼理論、VLSI設(shè)計(jì)、Ramsey理論、并行計(jì)算和分布式計(jì)算中.

設(shè)n為正整數(shù)，給出集合{0,1,2,…,n-1}的一個(gè)子集S(又稱(chēng)符號(hào)集)，即S?{0,1,2,…,n-1}，0?S.具有n個(gè)頂點(diǎn)的循環(huán)圖記為G(n,S)，如果它的任意2個(gè)頂點(diǎn)i與j相鄰當(dāng)且僅當(dāng)i-jmodn∈S.假設(shè)S={n1,n2,…,np}，ni∈{1,2,…,n-1}，則G(n,S)是一個(gè)度為p的正則圖.

引理1[13]若G(n,S)是一個(gè)具有n個(gè)頂點(diǎn)的循環(huán)圖，

S={n1,n2,…,np}n1

則

(ⅰ)當(dāng)p為奇數(shù)時(shí)，循環(huán)圖的能量

(ⅱ)當(dāng)p為偶數(shù)時(shí)，循環(huán)圖的能量

引理2[14]若G是一個(gè)具有n(n≥2)個(gè)頂點(diǎn)和m(m≥1)條邊的簡(jiǎn)單圖，則

其中

定理1若G(n,S)是一個(gè)具有n個(gè)頂點(diǎn)的循環(huán)圖，

S={n1,n2,…,np}n1

則

(ⅰ)當(dāng)p為奇數(shù)時(shí)，循環(huán)圖的無(wú)符號(hào)Laplacian能量

(ⅱ)當(dāng)p為偶數(shù)時(shí)，循環(huán)圖的能量

根據(jù)引理1，當(dāng)p為奇數(shù)時(shí)，

結(jié)合(1)式有

當(dāng)p為偶數(shù)時(shí)，結(jié)合(1)式有

定理2若G(n,S)是一個(gè)具有n個(gè)頂點(diǎn)的r-循環(huán)圖，則LE+(G(n,S))≤2r(n-1).

定理3若G(n,S)是一個(gè)具有n個(gè)頂點(diǎn)的r-循環(huán)圖，則

其中

根據(jù)引理2，定理3顯然成立，證明略去.

仍以循環(huán)圖G(12,S),S={1,6,11}為例，利用定理3可得LE+(G(12,S))≤47.76，結(jié)果與軟件計(jì)算結(jié)果相符.