雙圈圖補(bǔ)圖的距離譜半徑*

李遠(yuǎn)菁，李 丹，劉 康

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆烏魯木齊 830017)

0 引言

設(shè)G=(V(G),E(G)) 是一個(gè)簡(jiǎn)單連通圖, 其中V(G) 是圖G 的頂點(diǎn)集, E(G) 是圖G 的邊集.圖G 的頂點(diǎn)數(shù)定義為n=|V(G)|, 邊數(shù)定義為m=|E(G)|.圖G 的補(bǔ)圖為Gc=(V(Gc), E(Gc)), 其中V(Gc)=V(G),E(Gc)={vivj|vivj/∈E(G), ?vi, vj∈V(G)}.設(shè)vi, vj∈V(G), 若vivj∈E(G), 則vi, vj在圖G 中相鄰, 記作vi～vj; 否則vi, vj在圖G 中不相鄰, 記作vi?vj.圖G 中與點(diǎn)v 相鄰的頂點(diǎn)集稱為點(diǎn)v 在圖G 中的鄰集, 記作NG(v).NG[v]=NG(v)∪{v} 稱為點(diǎn)v 在圖G 中的閉鄰集.dG(v)=|NG(v)| 稱為點(diǎn)v 在圖G 中的度.點(diǎn)vi和vj之間最短路徑的長(zhǎng)度稱為點(diǎn)vi和點(diǎn)vj在圖G 中的距離, 記作dG(vi,vj).圖G 中任意兩點(diǎn)之間距離的最大值稱為圖G 的直徑,記作diam(G).圖G 的鄰接矩陣為A(G)=(aij)n×n,其中當(dāng)vi～vj時(shí), aij=1,否則aij=0.圖G 的距離矩陣為D(G)=(dG(vi,vj))n×n.圖G 的距離特征多項(xiàng)式為PG(λ)=|λIn-D(G)|.距離矩陣D(G)的特征值集合稱為圖G 的距離譜, 記λ1(D(G))≥λ2(D(G))≥···≥λn(D(G)) 是圖G 的距離譜的一個(gè)排序.矩陣M 特征值的模的最大值稱為矩陣M 的譜半徑.顯然, 圖G 的距離矩陣D(G) 是非負(fù)不可約的, D(G) 的最大特征值就是圖G 的距離譜半徑, 記作ρ(G).

相對(duì)圖的距離譜研究, 圖的補(bǔ)圖的距離譜研究很少.在n 階樹的補(bǔ)圖中, Lin 等[7]刻畫了距離譜半徑分別達(dá)到最大和最小的極圖, 并且刻畫了最小距離特征值分別達(dá)到最大和最小的極圖; Qin 等[8]在n 階單圈圖的補(bǔ)圖中刻畫了距離譜半徑達(dá)到最大的極圖, 且給出了直徑為3 的單圈圖的補(bǔ)圖的最小距離特征值達(dá)到最大的極圖.

本文主要研究n 階雙圈圖的補(bǔ)圖的距離矩陣,在Bn中不考慮圖D3,0,3,D3,0,3u(n-5),θ2,1,2,θ2,2,2和θ2,1,2u(n-4).設(shè)G 是一個(gè)n 階連通圖且Gc連通,若diam(G)≥4,則D(Gc)=Jn-In+A(G),否則D(Gc)≥Jn-In+A(G).令S={G|G ∈Bn, n ≥7, diam(G)=3 且D(Gc)＞Jn-In+A(G)}, 則S 中共有21 類圖, 見圖1.

圖1 S 中的21 類圖

1 預(yù)備知識(shí)

引理1[9]若M 是n 階非負(fù)不可約矩陣且n ≥2, 那么以下命題成立:

（1）矩陣M 的譜半徑ρ(M)≥0 且ρ(M) 是矩陣M 的單根;

（2）矩陣M 有屬于特征值ρ(M) 的正特征向量;

（3）矩陣M 的所有非負(fù)特征向量都屬于特征值ρ(M).

引理2[10]設(shè)M=(mij) 是一個(gè)n 階非負(fù)矩陣, ρ(M) 是距陣M 的譜半徑, Ri(M) 表示矩陣M 第i 行的行和.則

如果M 是不可約矩陣, 那么等號(hào)成立當(dāng)且僅當(dāng)R1(M)=R2(M)=···=Rn(M).在本節(jié)中, 將給出兩種圖變換來幫助完成本文.

引理3[8](圖變換1) 設(shè)圖G 是一個(gè)連通圖, uv 是圖G 的一條非懸掛割邊.設(shè)圖G1是通過收縮圖G 的邊uv 為一點(diǎn)u 并使點(diǎn)u 與點(diǎn)v 連接成懸掛邊得到的圖, 如圖2 所示, 則ρ(Gc1)＞ρ(Gc).

圖2 圖G 和圖G1

2 主要結(jié)果

引理5 設(shè)圖G ∈Dn(Dn∩S), X 是屬于ρ(Gc) 的Perron 向量.對(duì)于任意的正整數(shù)n ≥7, 必然存在G′∈Θn, 若圖G′c是連通圖, 則ρ(G′c)＞ρ(Gc).

情形5 h ≥4, k ≥2, l=1.對(duì)圖G 圈上的任意兩點(diǎn)運(yùn)用圖變換2, 通過比較這兩點(diǎn)對(duì)應(yīng)于ρ(Gc) 的Perron向量中分量的大小, 將分量較小的點(diǎn)連接的鄰邊去掉并使分量較大的點(diǎn)與這些鄰點(diǎn)相連, 不斷進(jìn)行上述的圖變換, 最終可得圖G3∈Θ2,1,2(情形1 中的圖) 或圖G4∈Θ2,2,2(情形2 中的圖) 或圖G5∈Θ3,1,2(情形3 中的圖)或圖G6∈Θ3,1,3(情形4 中的圖).由引理4 可知結(jié)論成立.

情形6 h ≥3, k ≥2, l=2.不斷對(duì)圖G 進(jìn)行與情形5 類似的圖變換, 最終可得圖G7∈Θ2,1,2(情形1 中的圖) 或圖G8∈Θ2,2,2(情形2 中的圖) 或圖G9∈Θ3,1,2(情形3 中的圖) 或圖G10∈Θ3,1,3(情形4 中的圖).由引理4 可知結(jié)論成立.

情形7 h ≥k ≥l ≥3.不斷對(duì)圖G 進(jìn)行與情形5 類似的圖變換, 最終可得圖G11∈Θ2,1,2(情形1 中的圖) 或圖G12∈Θ2,2,2(情形2 中的圖) 或圖G13∈Θ3,1,2(情形3 中的圖) 或圖G14∈Θ3,1,3(情形4 中的圖).由引理4可知結(jié)論成立.

綜上所述, 必然存在圖G′′∈S, 使得ρ(G′′c)＞ρ(Gc).

引理7 對(duì)于任意正整數(shù)n ≥6, p, q.則ρ(θc2,1,2uv(p,q))＞ρ(θc2,1,2u(p,q)).

證明令S2=Nθ2,1,2u(p,q)(u′){u}.設(shè)X 是屬于ρ(θc2,1,2u(p,q)) 的Perron 向量, 若xv≥xu′, 則

其中