輪圖的平衡性

李詩(shī)雅，馬曉玢

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

0 引言

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

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

1 相關(guān)引理

引理1.1[3]設(shè)v是G的任意頂點(diǎn)，則s(G-v)-1≤s(G)≤s(G-v)+1，當(dāng)且僅當(dāng)r(G-v)=r(G)或r(G-v)=r(G)-2時(shí)，s(G)=s(G-v).

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

若D為可逆矩陣，則

2 主要結(jié)果

記Wn是一個(gè)頂點(diǎn)集為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 設(shè)Wn是n+1階的輪圖，若n=1(mod4)，則s(Wn)=0，輪圖Wn平衡；若n≠1(mod4)，則s(Wn)≠0，輪圖Wn不平衡.

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

(i)當(dāng)n=0(mod2)時(shí)，刪去度為n的頂點(diǎn)得到圈Cn，根據(jù)引理1.1可知，

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

(1)

即有

-1≤s(Wn)≤1.

(2)

當(dāng)n=0(mod4)時(shí)，對(duì)于鄰接矩陣A，存在可逆的n+1階矩陣P，

使得PAPT=B，計(jì)算可得

則矩陣A與矩陣B等價(jià).即當(dāng)n=0(mod4)時(shí)，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)時(shí)，r(Wn)=n-1，s(Wn)≠0.

當(dāng)n=2(mod4)時(shí)，對(duì)于鄰接矩陣A，也存在可逆的n+1階矩陣P，

使得PAPT=B，計(jì)算可得

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

(ii)當(dāng)n=1(mod2)時(shí)，將圖Wn的鄰接矩陣A構(gòu)造為分塊矩陣：

當(dāng)n=1(mod4)時(shí)，矩陣D為n-1階實(shí)對(duì)稱(chēng)矩陣，且有

當(dāng)n=3(mod4)時(shí)，矩陣D也為n-1階實(shí)對(duì)稱(chēng)矩陣，且有

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

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