若干等能量圖族的構造①

王洪波

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

0 引 言

設G是一個頂點集為V={v1,v2,…,vn}，邊集為E的簡單圖.圖G的鄰接矩陣定義為A(G)=(aij)n×n，其中aij=1，若vi與vj相鄰；否則aij=0.A(G)的特征多項式被稱為G的特征多項式，記為ψ(G,λ)=det(λI-A(G))，其根也被稱為G的特征值.由于A(G)是實對稱的，故其特征值是實數[1].記G的全部互異特征值為λ1,λ2,…,λl，這些特征值的代數重數分別為m1,m2,…,ml，其中m1+m2+…+ml=n.G的全部互異特征值連同它們的重數被稱為G的譜，記為

圖的特征值的絕對值之和被定義為圖的能量.能量是一類重要的圖指標，與共軛碳氫分子的π-電子能量緊密關聯(lián).若兩個圖的能量相同，則稱這兩個圖是等能量的.與能量有關的問題被許多學者研究[2-3]，許多的文獻都給出了構造等能量圖的方法.Ramane等[4-5]利用線圖的性質給出兩個非同譜等能量無限圖族；Kwong等[7]利用刪邊運算給出許多對等能量圖(圖對中一個圖是另外一個圖的子圖)；Saroja等[6]給出了一些由完全圖構造而成的正則等能量圖；王洪波等[8]利用聯(lián)并圖的譜的性質給出一個構造等能量圖的方法.本文利用矩陣的相關性質構造了若干等能量圖族.

例如，若G=P3(長度為2的路)，m=4，則G(1),G(2),G(3),G(4),G(5)分別如圖1所示.

圖1

1 相關引理

若矩陣A=(aij)m×n，B=(bij)p×q.定義A和B的Kronecker積為

引理1[1]設A=(aij)n×n的特征值為λ1,λ2,…,λn，B=(bij)m×m的特征值為μ1,μ2,…,μm，則A?B的特征值為{λiμj|1≤i≤n,1≤j≤m}.

引理2 設A,B,C,D是n階方陣，則

證明：記左邊的行列式為D2nm，由Laplacian展開定理，將D2nm按第(m-1)n+1,(m-1)+2,…,mn,mn+1,…,(m+1)n列展開，易得

以此作遞推公式，即可得

2 等能量圖

定理1 設G的頂點數為n的簡單圖，G(1),G(2),G(3),G(4)是按前文方式構造的圖.則G(1),G(2),G(3),G(4)是等能量的且E(G(1))=E(G(2))=E(G(3))=E(G(4))=mE(G).

證明：設

對G(1),G(2),G(3),G(4)的頂點經過適當的排序，則G(1),G(2),G(3),G(4)的鄰接矩陣可以分別表示為

A(G(1))=diag(A(G),A(G),…,A(G)).

這里Jm是m階全1方陣.

這里A(G)=(aij)n×n.

Spec(G(2))=Spec(G(4))=

從而

(3)對G(3)，分以下兩種情形討論：

Spec(G(3))=

從而

情形2若m是奇數，

綜上所述，E(G(1))=E(G(2))=E(G(3))=E(G(4))=mE(G).證畢

定理2 設G是頂點數為n的簡單圖且其所有特征值的絕對值都不小于1，G(1),G(2),G(3),

G(4),G(5)是按前文方式構造的圖.則G(1),G(2),G(3),G(4),G(5)是等能量的且E(G(1))=E(G(2))=E(G(3))=E(G(4))=E(G(5))=mE(G).

證明：設

由定理1，G(1),G(2),G(3),G(4)是等能量的且E(G(1))=E(G(2))=E(G(3))=E(G(4))=mE(G).

對G(5)的頂點經過適當的排序，(1)當m是偶數時，G(5)的鄰接矩陣可以表示為

從而

Spec(G(5))=

故當|λi|≥1(i=1,2,…,l)時，

(2)當m是奇數時，G(5)的鄰接矩陣可以表示為

A(G(5))=

由引理2，引理3，經計算知，

ψ(G(5),λ)=

(λIn-A(G)).

從而

Spec(G(5))=

故當|λi|≥1(i=1,2,…,l)時，