輪圖的平衡性

李詩雅，馬曉玢

(安徽理工大學數學與大數據學院，安徽 淮南 232001)

0 引言

本文只研究無重邊無環的簡單圖.記G=(V(G),E(G))是一個頂點集和邊集分別為V={v1,v2,…,vn}和E=E(G)的n階簡單圖.圖G的鄰接矩陣A(G)=(aij)n×n，其中，若vi,vj相鄰，則aij=1；否則aij=0.鄰接矩陣A(G)的秩為圖G的秩，記為r(G).鄰接矩陣A(G)的特征值為圖G的特征值.圖G的正負慣性指數和零度指其鄰接矩陣A(G)所有特征值中正、負和零特征值的個數，分別用p(G),n(G),η(G)表示.正、負慣性指數之差稱為符號差，用s(G)表示.若s(G)=0，則稱這個圖是平衡的.顯然，任意二部圖是平衡的，但反之不成立.因而一個自然的問題就是刻畫所有的平衡圖.

記n為一個整數，一個n-圈Cn定義為一個包含n個頂點和n條邊的圖，其頂點集和邊集分別記為V={a1,a2,…,an}，E={e1,e2,…,en}，對于每個i(1≤i≤n)，ei的端點是ai-1和ai.由一個n-圈Cn添加一個新的頂點，并將該頂點與圈的所有n個頂點相連，得到的圖稱為輪圖，記為Wn.

1 相關引理

引理1.1[3]設v是G的任意頂點，則s(G-v)-1≤s(G)≤s(G-v)+1，當且僅當r(G-v)=r(G)或r(G-v)=r(G)-2時，s(G)=s(G-v).

引理1.2[4]令n=4q+r，n≥3，其中，n,r都是正整數，q為非負整數，且3≤r≤6.則

若D為可逆矩陣，則

2 主要結果

記Wn是一個頂點集為V(Wn)={v0,v1,v2,…,vn}，邊集為E(Wn)={v0vj|j=1,2,…,n}∪{v1,vn}∪{vjvj+1|j=1,2,…,n-1}的n+1階的n-輪圖.

定理2.1 設Wn是n+1階的輪圖，若n=1(mod4)，則s(Wn)=0，輪圖Wn平衡；若n≠1(mod4)，則s(Wn)≠0，輪圖Wn不平衡.

證明 首先將n的取值分為下面兩種情況：

(i)當n=0(mod2)時，刪去度為n的頂點得到圈Cn，根據引理1.1可知，

s(Cn)-1≤s(Wn)≤s(Cn)+1,

(1)

即有

-1≤s(Wn)≤1.

(2)

當n=0(mod4)時，對于鄰接矩陣A，存在可逆的n+1階矩陣P，

使得PAPT=B，計算可得

則矩陣A與矩陣B等價.即當n=0(mod4)時，r(A)=r(B)=n-1，即η(Wn)=2，r(Wn)=n-1.

由等式p(Wn)+n(Wn)=r(Wn)可得，p(Wn)+n(Wn)=n-1.由式(2)可知，n=0(mod4)時，r(Wn)=n-1，s(Wn)≠0.

當n=2(mod4)時，對于鄰接矩陣A，也存在可逆的n+1階矩陣P，

使得PAPT=B，計算可得

即當n=2(mod4)時，r(A)=r(B)=n，η(Wn)=0，r(Wn)=n+1.由等式p(Wn)+n(Wn)=r(Wn)可得，p(Wn)+n(Wn)=n+1.由式(2)可知，當n=2(mod4)時，r(Wn)=n+1，s(Wn)≠0.

(ii)當n=1(mod2)時，將圖Wn的鄰接矩陣A構造為分塊矩陣：

當n=1(mod4)時，矩陣D為n-1階實對稱矩陣，且有

當n=3(mod4)時，矩陣D也為n-1階實對稱矩陣，且有

當n=1(mod2)時，刪去圖Wn中度為n的頂點得到圈Cn，由引理1.2可知，此時r(Cn)=n，即r(Wn)=n+1=r(Cn)+1，則s(Wn)=s(Cn)+1或s(Wn)=s(Cn)-1.而當r(W5)=6=r(C5)+1時，有s(W5)=0≠s(C5)+1.當r(W3)=4=r(C3)+1時，有s(W3)=-2≠s(C3)+1.故s(Wn)=s(Cn)+1不成立，而s(Wn)=s(Cn)-1成立.因此，當n=1(mod4)時，有s(Cn)=1，s(Wn)=s(Cn)-1=0.當n=3(mod4)時，s(Cn)=-1，s(Wn)=s(Cn)-1=-2≠0.

綜上所述，當n=1(mod4)時，有s(Wn)=0，則輪圖Wn是平衡圖；當n≠1(mod4)時，有s(Wn)≠0，則輪圖Wn不是平衡圖.