循環(huán)圖的無符號Laplacian能量的上界*

徐幼專

(邵陽廣播電視大學,湖南 邵陽 422000)

若G是一個具有n個頂點和m條邊的簡單連通圖，則

(1)

等式成立當且僅當G是一個正則圖;

(2)

等式成立當且僅當G是一個空圖或是一條邊加n-2個孤立點所構(gòu)成的圖.

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

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

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

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

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

則

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

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

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

其中

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

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

則

(ⅰ)當p為奇數(shù)時，循環(huán)圖的無符號Laplacian能量

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

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

結(jié)合(1)式有

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

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

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

其中

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

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