朱銀芬，王國平，陳 星

(1.新疆工程學(xué)院數(shù)理學(xué)院，烏魯木齊 830029;2.新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，烏魯木齊830017)

如果一個(gè)連通圖G的點(diǎn)集是V(G)={v1，v2，…，vn}，那么圖G的距離矩陣D(G)=(dij)，其中dij表示點(diǎn)vi與vj之間的距離.令TrG(vi)表示點(diǎn)vi到圖G中其它所有點(diǎn)的距離之和，Tr(G)表示對(duì)角線位置的元素是TrG(vi)的對(duì)角矩陣.

圖G的距離拉普拉斯矩陣及距離無符號(hào)拉普拉斯矩陣分別被表示為L(zhǎng)D(G)=Tr(G)-D(G)與QD(G)=Tr(G)+D(G)，它們的最大特征值λL(G)和λQ(G)分別是圖G的距離拉普拉斯譜半徑與距離無符號(hào)拉普拉斯譜半徑．

Aouchiche和Hansen在文獻(xiàn)[1]中引入了圖的距離拉普拉斯譜與距離無符號(hào)拉普拉斯譜的概念，并且在文獻(xiàn)[2]中證明了樹中星圖具有最小距離拉普拉斯譜半徑.近年來，關(guān)于距離拉普拉斯譜與距離無符號(hào)拉普拉斯譜的研究已經(jīng)有了長(zhǎng)足的進(jìn)展.Xing與Zhou[3]確定了雙圈圖中具有最小距離譜半徑與最小距離無符號(hào)拉普拉斯譜半徑的唯一圖.文獻(xiàn)[4]確定了在樹、單圈圖、雙圈圖、給定懸掛點(diǎn)數(shù)與連通度的圖中具有最小距離無符號(hào)拉普拉斯譜半徑的圖.Liu與Lu[5]確定了給定團(tuán)數(shù)的距離無符號(hào)拉普拉斯譜半徑的界.Lin和Zhou[6]刻畫了在給定懸掛點(diǎn)數(shù)與邊連通度的圖中具最小的距離拉普拉斯譜半徑的唯一圖的特性.牛愛紅等[7]確定了給定匹配數(shù)或給定連通度的二部圖中具有最小距離拉普拉斯譜半徑的極圖．

本文確定了給定匹配數(shù)的圖的距離無符號(hào)拉普拉斯譜半徑的下界．

1 引理

先給出一些已知的結(jié)果．

引理1[1]圖G是連通圖，若uv?E(G)，那么λQ(G+uv)<λQ(G)．

引理2[1]設(shè)圖G是n階連通圖，那么λQ(G)≥λQ(Kn)=2(n-1)．

引理4[8]設(shè)A1與A2是n階實(shí)對(duì)稱矩，那么

λn(A2)+λi(A1)≤λi(A1+A2)，

其中λi(A)是A的第i大特征值．

引理5[8]設(shè)A是n階實(shí)對(duì)稱矩陣，M是A的s(s

λi+n-s(A)≤λi(M)≤λi(A)(1≤i≤s)，

其中λi(A)是A的第i大特征值.

若有X?V(G)，那么圖G的子圖G-X是將圖G的X中的點(diǎn)與X點(diǎn)相關(guān)聯(lián)的邊同時(shí)刪除后得到的.圖G的一個(gè)匹配是圖G中不相鄰的邊的集合，那么所有匹配中含有最大的邊數(shù)叫做圖G的匹配數(shù).若圖G的某個(gè)連通分支的點(diǎn)數(shù)是奇數(shù)，那么稱這個(gè)連通分支是圖G的奇連通分支;否則，稱這個(gè)連通分支是偶連通分支．

引理6[9-10]如果圖G是匹配數(shù)為m的n階圖，那么

n-2m=max{o(G-X)-|X|:X?V(G)}，

其中o(G-X)是圖G-X的奇連通分支數(shù)．

引理7[11]如果圖G是連通圖，那么λQ(G)>λL(G)．

2 定理及推論

?

Kn，則由引理1知λQ(G)>λQ(Kn)．

設(shè)G-X0的所有連通分支為H1，H2，…，Hk，Hk+1，…，Ht，其中H1，H2，…，Hk是G-X0的奇連通分支，Hk+1，…，Ht是G-X0的偶連通分支．

這樣，λQ(G)>2n-m．

下面假定s

情況1t=k.

在這種情況下G-X0的所有連通分支H1，H2，…，Hk都為奇連通分支.設(shè)|V(Hi)|=ni，則ni是奇數(shù)(i=1，2，…，k)．

下面先就G?Ks∨(Kn1∪Kn2∪…∪Knk)的情況進(jìn)行驗(yàn)證．

為方便書寫，不妨假定n1≤n2≤…≤nk.若n1=…=nk=1，則n=k+s．

注意到n-2m=k-s，這樣就有s=m，這與s

令M={v1u1，v2u2，…，vsus}∪Mp∪Mp+1∪…∪Mk，則M就是G的一個(gè)匹配．這樣，

注意到當(dāng)p≤i≤k時(shí)，ni≥np.因此，

若p≥3，則n1=n2=1.設(shè)u與v分別是Kn1與Kn2中的那個(gè)點(diǎn).在QD(G)中取2×2階主子矩陣:

因?yàn)閗≥3，所以m≥s+1，進(jìn)而

TrG(v)=TrG(u)=

s+2(n-s-1)≥2n-m-1，

令

由引理4與引理5，得到

λQ(G)≥λQ(A)≥λQ(A′)=2n-m+1>2n-m.

若p=2，那么n1=1，而對(duì)于所有的2≤i≤k都有ni≥3.設(shè)u∈Kn1且v∈Ks，類似可得，在QD(G)中取2×2階主子矩陣：

因?yàn)閗≥3，于是得到m≥s+2.進(jìn)而

TrG(v)=s+2(n-s-1)≥2n-m，

且

TrG(u)=n-1．

令

由引理4與引理5，得到

λQ(G)≥λQ(B)≥λQ(B′)=

2n-m.

若p=1，則對(duì)于所有的1≤i≤k都有ni≥3.下面針對(duì)k≥3的取值情況分類討論．

若k≥4，設(shè)u和v是Kn1中不同的兩個(gè)點(diǎn).在QD(G)中取2×2階主子矩陣:

TrG(v)=TrG(u)=
s+n1-1+2(n-s-n1)≥2n-m.

令

由引理4與引理5得

λQ(G)≥λQ(C)≥λQ(C′)=

2n-m+1>2n-m.

當(dāng)k=3且n3=3時(shí)，設(shè)u∈Kn1，v∈Kn2.在QD(G)中取2×2階主子矩陣：

TrG(v)=TrG(u)=s+n1-1+2(n-s-n1)
≥2n-s-4≥2n-m-1.

令

由引理4與引理5，得

λQ(G)≥λQ(D)≥λQ(D′)=

2n-m+1>2n-m.

當(dāng)k=3且n3≥5時(shí)，設(shè)u和v是Kn1中不同的兩個(gè)點(diǎn).在QD(G)中取2×2階主子矩陣:

進(jìn)而有

TrG(v)=TrG(u)=

s+n1-1+2(n-s-n1)≥2n-m.

令

由引理4與引理5，得

λQ(G)≥λQ(E)≥λQ(E′)=2n-m+1>2n-m.

綜上所述，當(dāng)G?Ks∨(Kn1∪Kn2∪…∪Knk)時(shí)，λQ(G)>2n-m.當(dāng)GKs∨(Kn1∪Kn2∪…∪Knk)時(shí)，由引理1可知，

λQ(G)>λQ(Ks∨(Kn1∪Kn2∪…∪Knk))，

進(jìn)而有λQ(G)>2n-m．

情況2t>k．

此時(shí)，G-X0不僅有k個(gè)奇連通分支，且有t-k個(gè)偶連通分支.將圖G的每一個(gè)偶連通分支Hj(k+1≤j≤t)中的某個(gè)點(diǎn)，與奇連通分支H1中的某個(gè)點(diǎn)連接一條邊后得到的圖記作G′.

顯然G′-X0也有k個(gè)奇連通分支，且圖G′的最大匹配數(shù)m(G′)≥m.由引理6，有

n-2m≥n-2m(G′)≥o(G′-X0)-|X0|=

o(G-X0)-|X0|=n-2m.