王洪波, 林 泓

(集美大學(xué)理學(xué)院， 福建 廈門 361021)

0 引言

設(shè)G=(V,E) 是頂點集為V={v1,v2, …,vn}而邊集為E的簡單圖.G的鄰接矩陣定義為A(G)=(aij)n×n， 其中aij=1， 若vi與vj相鄰； 否則aij=0. 由于A(G)是實對稱的， 故其特征值是實數(shù)[1]. 設(shè)λi1,λi2, …,λil是A(G)的全部互異特征值， 它們的代數(shù)重數(shù)分別為m1,m2, …,ml， 這里m1+m2+…+ml=n. 則A(G)的所有互異特征值連同它們的重數(shù)被稱為G的譜.

定義G的能量為圖的鄰接矩陣的特征值的絕對值之和. 圖的能量作為一類在化學(xué)中有重要應(yīng)用的圖指標(biāo)， 已被許多學(xué)者所研究[2-3].

具有相同的譜的兩個非同構(gòu)圖稱為同譜圖. 若兩個非同構(gòu)圖有相同的能量， 則稱它們?yōu)榈饶芰康? 在許多的文獻(xiàn)中都有等能量圖的例子[4-7]， 本文將介紹一種構(gòu)造等能量圖的方法. 先給出若干正則圖的聯(lián)并圖的譜， 它的譜是由正則圖的譜(去掉每個正則圖的第一個最大特征值)和一個由圖G決定的輔助矩陣的特征值組成. 接著利用這個刻劃給出了一個利用正則圖的聯(lián)并圖構(gòu)造等能量圖的方法. 作為應(yīng)用， 最后給出了一些等能量圖的例子.

1 聯(lián)并圖

設(shè)G和H是兩個圖，G和H的并圖G∪H定義為：V(G∪H)=V(G)∪V(H)，E(G∪H)=E(G)

圖1 聯(lián)并圖K2[C3, C4]Fig.1 Joined union graph K2[C3, C4]

∪E(H). 設(shè)G是頂點數(shù)為n的簡單圖，Gi=(Vi,Ei)，i=1, 2, …,n是任意n個簡單圖.G1,G2, …,Gn的聯(lián)并圖G[G1,G2, …,Gn]=(W,F) 定義為：

顯然聯(lián)并圖G[G1,G2, …,Gn] 就是在G1,G2, …,Gn的并圖上再添加一些新邊： 若G中的頂點vi與vj相鄰， 則將Gi的所有頂點與Gj的所有頂點相連.

例如， 在C3∪C4中將C3的所有頂點和C4的所有頂點相連就得到K2[C3,C4]， 如圖1所示.

2 聯(lián)并圖的譜

定理1設(shè)G=(V,E) 是頂點數(shù)為n的簡單圖， 其鄰接矩陣為A(G)=(aij)n×n， 而Gi=(Vi,Ei) (i=1, 2, …,n) 是頂點數(shù)為mi的ri-正則圖， 其鄰接矩陣的特征值為ri=λi1≥λi2≥…≥λimi. 則λij(i=1, 2, …,n;j=2, 3, …,mi) 及矩陣A*的特征值就是聯(lián)并圖G[G1,G2, …,Gn] 的全部特征值， 這里

證明 記H=G[G1,G2, …,Gn]. 則H的鄰接矩陣具有如下的形式：

其中:A(Gi) 是Gi的鄰接矩陣；Jmi×mj是mi×mj全1矩陣，i,j=1, 2, …,n.

對任意給定的i∈{1, 2, …,n}， 設(shè)ui1(mi維全1向量， 記為1mi),ui2, …,uimi為A(Gi) 的對應(yīng)于λi1,λi2, …,λimi的mi個互相正交的特征向量.

由此可知，z1,z2, …,zn滿足方程組

因為z1,z2, …,zn不全為零. 故

(1)

即μ是矩陣A*的特征值. 因為H的任意相異于λij(i=1, 2, …,n;j=2, 3, …,mi) 的特征值均滿足(1). 故矩陣A*的特征值是H的所有異于λij(i=1, 2, …,n;j=2, 3, …,mi) 的特征值.

證畢.

3 等能量圖

定理2設(shè)G=(V,E)是具有n個頂點的簡單圖， 對i=1, 2, …,n，Gi和Hi是頂點數(shù)為mi的ri-正則等能量圖. 則

E(G[G1,G2, …,Gn])=E(G[H1,H2, …,Hn])

證明 設(shè)G的鄰接矩陣為A(G)=(aij)n×n. 因為Gi和Hi有相同的頂點數(shù)mi和度數(shù)ri， 由定理1可知，G[G1,G2, …,Gn]和G[H1,H2, …,Hn]有相同的輔助矩陣

現(xiàn)假設(shè)A*的特征值的絕對值之和為M且對任意的正整數(shù)i(1≤i≤n)，A(Gi)的特征值為ri=λi1≥λi2≥…≥λimi，A(Hi) 的特征值為ri=μi1≥μi2≥…≥μimi. 則

因為E(Gi)=E(Hi)(i=1, 2, …,n)， 所以

E(G[G1,G2, …,Gn])=E(G[H1,H2, …,Hn])

證畢.

4 例子

例1設(shè)G是一個圖，L1(G)=L(G) 是G的線圖， 用遞歸法可以定義

Lk(G)=L(Lk-1(G)),k≥2

Ramane等證明如下結(jié)論[4]:

設(shè)G1,G2是兩個頂點數(shù)為n， 正則度為r≥3 的正則圖， 則對任意k≥2，Lk(G1)，Lk(G2)具有相同的能量.

顯然，Lk(G1)，Lk(G2)均是正則圖， 且它們的頂點數(shù)和正則度均相同.

進(jìn)一步地， Ramane， Gutman等證明如下結(jié)論[5]:

例如G[Lk(G1),Lk(G1), …,Lk(G1)]，G[Lk(G1),Lk(G1), …,Lk(G2)]， …，G[Lk(G1),Lk(G2), …,Lk(G2)]，G[Lk(G2),Lk(G2), …,Lk(G2)] 就是n+1個等能量圖.

例2設(shè)Kp, p是頂點數(shù)為2p的完全二部圖，P是Kp, p的完美匹配， 則Kp, p-P和Kp∪Kp都是頂點數(shù)為2p， 度為p-1 的正則圖. 可以證明[6]:Kp, p-P和Kp∪Kp具有相同的能量4(p-1). 對任意一個頂點數(shù)為n的簡單圖G， 由定理2可知，G[Kp, p-P,Kp, p-P, …,Kp, p-P],G[Kp, p-P,Kp, p-P, …,Kp, p-P,Kp∪Kp], …,G[Kp, p-P,Kp∪Kp, …,Kp∪Kp],G[Kp∪Kp,Kp∪Kp, …,Kp∪Kp] 是n+1 個等能量圖.