馮小蕓, 陳 旭, 王國(guó)平

(新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，烏魯木齊 830017)

0 引言

連通圖的最小無(wú)符號(hào)拉普拉斯特征值已經(jīng)被廣泛研究。Cardoso 等[1]給出了所有非二部圖的連通圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。Guo 等[2]給出圖的最小無(wú)符號(hào)拉普拉斯特征值的下界。Guo 和Zhang[3]確定了給定最大度的所有非二部圖的連通圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。Fan 等[4]確定了帶有懸掛點(diǎn)的所有非二部圖的連通圖中最小無(wú)符號(hào)拉普拉斯特征值分別是最大和最小的唯一圖。Guo 等[5]確定了所有單圈圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。Wang 和Fan[6]確定了在一類給定非二部圖作為誘導(dǎo)子圖且有固定階的連通圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。Yu 等[7]確定了所有非二部圖的連通雙圈圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。Yu 等[8]分別確定了給定匹配數(shù)和邊覆蓋數(shù)的所有非二部圖的連通圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。Wen 等[9]分別給出了帶有穩(wěn)定數(shù)和覆蓋數(shù)的所有非二部圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。

設(shè)G= (V(G),E(G))是一個(gè)連通簡(jiǎn)單圖，可定義G的補(bǔ)圖Gc= (V(Gc),E(Gc))，其中V(Gc)=V(G)和E(Gc)={xy:x,y ∈V(G),xy/∈E(G)}。若|E(G)|=|V(G)|+1，則稱G是一個(gè)雙圈圖。我們定義K1,n?1是帶有n個(gè)點(diǎn)的星圖，若K1,n?1+ 2e是從K1,n?1中連接兩對(duì)不同的懸掛點(diǎn)對(duì)而得到的圖，由于K1,n?1+2e的補(bǔ)圖(K1,n?1+2e)c含有一個(gè)孤立點(diǎn)，所以(K1,n?1+2e)c不連通。顯然，不少于12 個(gè)點(diǎn)的雙圈圖的補(bǔ)圖是非二部圖，所以我們僅考慮不少于12 個(gè)點(diǎn)的除了K1,n?1+2e(n ≥12)之外的雙圈圖的補(bǔ)圖。

Li 和Wang[10]確定除星圖K1,n?1的所有樹(shù)的補(bǔ)圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。Yu 等[11]確定了除圖K1,n?1+e的所有單圈圖的補(bǔ)圖中最小無(wú)符號(hào)拉普拉斯特征值是最小的唯一圖。本文中，我們給出兩種圖變換，并且應(yīng)用它們確定了帶有n ≥12 個(gè)點(diǎn)除了K1,n?1+2e的所有雙圈圖的補(bǔ)圖中最小無(wú)符號(hào)拉普拉斯特征值取最小的唯一圖。

1 主要結(jié)論

假設(shè)G是點(diǎn)集為V(G) ={v1,v2,···,vn}的圖，下文我們將λn(G)記為λ(G)。令X=(X1,X2,···,Xn)T是一個(gè)單位向量，其中Xi=X(vi)(1≤i ≤n)，這樣有

(2)式中的等號(hào)成立，當(dāng)且僅當(dāng)X是Q(G)的關(guān)于特征值λ(G)的特征向量。

本文將帶有n個(gè)點(diǎn)的圖的點(diǎn)集記為{v1,v2,···,vn}，令X= (X1,X2,···,Xn)T是一個(gè)單位向量，其中Xi=X(vi)(1≤i ≤n)，且X1≥X2≥···≥0≥···≥Xn。

引理1[10]設(shè)X如上所示，其中X1>0 和Xn＜0，則對(duì)于任意的1≤i,j ≤n，有

將帶有n個(gè)點(diǎn)的所有連通雙圈圖的連通補(bǔ)圖的集合記為(n ≥12)，那么對(duì)于任意G ∈，則有λ(G)>0。

將圖G中點(diǎn)vi和點(diǎn)vj之間最短路的長(zhǎng)度稱為它們之間的距離，記為dG(vi,vj)。

設(shè)Gk(p,q)(1≤k ≤12)，如圖1 所示。

圖1 Gk(p,q)(1 ≤k ≤12)

我們令b-圖是由一條路和兩個(gè)不相交的圈組成的圖，其路的兩個(gè)端點(diǎn)分別屬于兩個(gè)不相交的圈中的點(diǎn)。令∞-圖是由兩個(gè)相交的圈組成的圖，其只有一個(gè)公共的交點(diǎn)。令θ-圖是由兩個(gè)相交的圈組成的圖，其中至少有兩個(gè)交點(diǎn)。顯然，雙圈圖是b-圖，∞-圖和θ-圖其中一個(gè)粘貼樹(shù)而得到的圖。

設(shè)G是一個(gè)帶有n個(gè)點(diǎn)的圖，其中v1vl1vl2···vltvn是v1和vn在圖G中最短的路。令X= (X1,X2,···,Xn)T，其中X1> 0 和Xn＜ 0。在圖G中，如果(X1+Xl2)2≥(Xn+Xl1)2，那么刪除邊vl1vl2，同時(shí)增加邊v1vl2，否則就增加邊vnvl1，我們稱上述過(guò)程為圖G的T1-變換。通過(guò)對(duì)圖G做一系列T1-變換得到的結(jié)果圖記為GT1，現(xiàn)在我們使用T1-變換證明下面結(jié)論。

引理2設(shè)H′={Gk(p,q)|1≤k ≤12}。若Gc ∈，則GT1∈H′，或者dGT1(v1,vn)≤2。

證明 如果G ∈H′或dG(v1,vn)≤2，那么結(jié)論自然成立。假設(shè)G/∈H′且dG(v1,vn)>2，則可分四種情況進(jìn)行討論。

情況1v1和vn在圖G的同一個(gè)圈上。

對(duì)圖G一直做T1-變換可知，dGT1(v1,vn)≤2。

情況2v1和vn分別屬于圖G的兩個(gè)圈。

顯然，圖G是b-圖或∞-圖粘貼樹(shù)而得到的。對(duì)G做一系列T1-變換可得，結(jié)果圖GT1是由θ-粘貼樹(shù)而得到的或者dGT1(v1,vn)≤dG(v1,vn)?1。如果前者成立，那么根據(jù)情況1 可證結(jié)論是正確的，否則重復(fù)上述過(guò)程，最終可以確定，結(jié)論是正確的。

情況3v1和vn分別在圖G的圈上和樹(shù)上。

不失一般性的假設(shè)v1在樹(shù)上和vn在圈上，對(duì)圖G做一系列的T1-變換可得，v1和vn是在GT1的同一個(gè)圈上，或者dGT1(v1,vn)≤dG(v1,vn)?1。如果前者成立，那么根據(jù)情況1 可證結(jié)論是正確的，否則重復(fù)上述過(guò)程，最終可以確定，結(jié)論是正確的。

情況4v1和vn都在圖G的樹(shù)上。

對(duì)圖G做一系列T1-變換可得，v1和vn分別在圖GT1的圈上和樹(shù)上，或dGT1(v1,vn)≤dG(v1,vn)?1。如果前者成立，那么根據(jù)情況3 可證結(jié)論是正確的，否則重復(fù)上述過(guò)程，最終可以確定，結(jié)論是正確的。

如果X=(X1,X2,···,Xn)T滿足XTQ(G)X=λ(G)，那么稱X是G的單位無(wú)符號(hào)拉普拉斯特征向量，這樣對(duì)于任意1≤i ≤n，有

其中NG(vi)是圖G中點(diǎn)vi的鄰域，方程(3)也被稱為圖G的無(wú)符號(hào)拉普拉斯特征方程。

令I(lǐng)n是一個(gè)n階單位矩陣，則Q(G)?λ(G)In是一個(gè)半正定矩陣，所以我們可以令X= (X1,X2,···,Xn)T是圖G的一個(gè)單位無(wú)符號(hào)拉普拉斯特征向量，且X1≥X2≥···≥Xn，這時(shí)X1>0 和Xn＜0。

令θ4和θ5分別是帶有4 個(gè)點(diǎn)和5 個(gè)點(diǎn)的θ-圖，令∞5和∞6分別是帶有5 個(gè)點(diǎn)和6 個(gè)點(diǎn)的∞-圖，令b6和b7分別是帶有6 個(gè)點(diǎn)和7 個(gè)點(diǎn)的b-圖，并且這些圖的兩個(gè)圈的長(zhǎng)度都是3。

設(shè)帶有n個(gè)點(diǎn)的圖H是從θ4、θ5、∞5、∞6、b6和b7中一個(gè)粘貼樹(shù)而得到的，我們可以找到一個(gè)懸掛點(diǎn)vs，并且它的鄰點(diǎn)vt既不是v1也不是vn。令X=(X1,X2,···,Xn)T，其中X1>0 和Xn＜0。在圖H中，如果(X1+Xs)2≥(Xn+Xs)2，那么刪除邊vtvs，同時(shí)增加邊v1vs，否則就增加邊vnvs，我們稱上述過(guò)程是圖H的T2-變換，對(duì)圖H做一系列的T2-變換得到的結(jié)果圖記為HT2。結(jié)合T1-變換和T2-變換可證下面重要結(jié)論。

令圖Hi(1≤i ≤7)，如圖2 所示vn。

圖2 Hi(1 ≤i ≤7)

引理3設(shè)H′={Hi|1≤i ≤7}，圖Gc ∈Ccn(n ≥12)，則存在圖H ∈H′∪H′′，滿足λ(Gc)≥λ(Hc)。

證明 記H=H′∪H′′，讓X= (X1,X2,···,Xn)T是Gc的單位無(wú)符號(hào)拉普拉斯特征向量，其中X1≥X2≥··· ≥Xn，這時(shí)X1> 0 和Xn＜ 0。如果G ∈H，那么結(jié)論自然成立。因此，假設(shè)G/∈H。

如果dG(v1,vn)> 2，那么對(duì)G做一系列T1-變換得到的結(jié)果圖記為GT1。結(jié)合引理2 可知，GT1∈H，或GT1/∈H，但dGT1(v1,vn)≤2。如果是前者成立，那么結(jié)合方程(1)和引理1，可得

現(xiàn)在假設(shè)后者成立，則分兩種情況討論GT1。

情況1dGT1(v1,vn)=1。

情況1.1v1和vn在同一個(gè)帶有t+2 個(gè)點(diǎn)的圈Ct+2上。

當(dāng)t ≥2 時(shí)，可以令Ct+2=v1vnvl1vl2···vltv1。如果(X1+Xl1)2≥(Xn+Xl2)2，那么刪除邊vl1vl2和增加邊v1vl1，否則增加邊vnvl2，在做一系列上述變換后可得一個(gè)包含圈C3=v1vnvl1v1的圖。設(shè)vs1vs2···vskvs1是圖G11的另一個(gè)圈，則如果(X1+Xs2)2≥(Xn+Xs1)2，那么刪除邊vs1vs2和增加邊v1vs2，否則增加邊vnvs1，通過(guò)做一系列上述變換得到的圖～G同構(gòu)于θ4或∞5粘貼樹(shù)而得到的圖。如果～G/∈H，那么通過(guò)對(duì)圖～G做一系列T2-變換得到的圖～GT2是同構(gòu)于圖2 的H1、H2和H3中某一個(gè)圖。

情況1.2v1和vn分別在不同的圈上。

顯然，GT1是由b-圖粘貼樹(shù)而得到的。設(shè)GT1包含圈Ct+1=v1vl1vl2···vltv1，則當(dāng)t ≥3 時(shí)，如果(X1+Xl2)2≥(Xn+Xl1)2，那么刪除邊vl1vl2和增加邊v1vl2，否則增加邊vnvl1可得圖。如果v1和vn是在 圖G21的同一個(gè)圈上，那么可以使用情況1.1，否則繼續(xù)做一系列上述變換可得一個(gè)包含圈C3=v1vl1vl2v1的圖。設(shè)vnvs1vs2···vskvn是圖的另一個(gè)圈，如果(Xn+Xs2)2≥(X1+Xs1)2，那么刪除邊vs1vs2和增加邊vnvs2，否則增加邊v1vs1可得圖。如果v1和vn在圖G23的同一個(gè)圈上，那么可使用情況1.1，否則繼續(xù)通過(guò)做一系列上述變換得到的圖是b6粘貼樹(shù)而得到的。如果/∈H，那么通過(guò)對(duì)做一系列T2-變換得到的圖是同構(gòu)于圖2 中H4。

情況1.3v1和vn分別在圈上和樹(shù)上。

不失一般性的假設(shè)v1在圈上和vn在樹(shù)上，否則將X替換為?X，則GT1包含圈Ct+1=v1vl1vl2···vltv1。當(dāng)t ≥3 時(shí)，如果(X1+Xl2)2≥(Xn+Xl1)2，那么刪除邊vl1vl2和增加邊v1vl2，否則增加邊vnvl1可得圖G31。如果v1和vn在圖的同一個(gè)圈上，那么可使用情況1.1，否則繼續(xù)做一系列上述變換可得一個(gè)包含圈C3=v1vl1vl2v1的圖。設(shè)vs1vs2···vskvs1是圖的另一個(gè)圈，則如果(X1+Xs2)2≥(Xn+Xs1)2，那么刪除邊vs1vs2和增加邊v1vs2，否則增加邊vnvs1可得圖。如 果v1和vn屬 于中的圈，那么可以使用情況1.1 或情況1.2，否則繼續(xù)通過(guò)做一系列上述變換得到的圖是θ4或∞5粘貼樹(shù)而得到的。如果/∈H，那么通過(guò)對(duì)圖做一系列T2-變換得到的圖是同構(gòu)于圖2 的H5、H6和H7中一個(gè)粘貼樹(shù)而得到的圖。

情況1.4v1和vn在同一個(gè)樹(shù)T上。

設(shè)樹(shù)T粘貼在圈Ck中點(diǎn)vlm，現(xiàn)考察路vnv1vl1vl2···vlm。如果(X1+Xl2)2≥(Xn+Xl2)2，那么刪除邊vl1vl2和增加邊v1vl2，否則增加邊vnvl2，在做一系列上述變換后可知道，點(diǎn)vl1是在圈vl1vs2···vskvl1上。如果(X1+Xs2)2≥(Xn+Xs2)2，那么刪除邊vl1vs2

和增加邊v1vs2，否則增加邊vnvs2可得圖。這時(shí)，在圖中，點(diǎn)v1和點(diǎn)vn是在同一個(gè)圈上或者點(diǎn)v1和點(diǎn)vn分別在圈上和樹(shù)上。如果前者成立，那么使用情況1.1，否則就使用情況1.3。

情況2dGT1(v1,vn)=2。

情況2.1v1和vn在同一個(gè)圈Ct+3上。

當(dāng)t ≥2 時(shí)，可以設(shè)Ct+3=v1vtvnvl1vl2···vltv1。如果(X1+Xl1)2≥(Xn+Xl2)2，那么刪除邊vl1vl2和增加邊v1vl1，否則增加邊vnvl2，通過(guò)做一系列上述變換可得一個(gè)含有圈C4=v1vtvnvl1v1的圖。設(shè)vs1vs2···vskvs1是圖的另一個(gè)圈，則如果(X1+Xs2)2≥(Xn+Xs1)2，那么刪除邊vs1vs2和增加邊v1vs2，否則增加邊vnvs1，通過(guò)做一系列上述變換得到的圖是θ5或∞6粘貼樹(shù)而得到的。如果/∈H，那么通過(guò)對(duì)做一系列T2-變換得到的圖是同構(gòu)于圖1 的G1(p,q)、G2(p,q)和G3(p,q)中一個(gè)圖。

情況2.2v1和vn分別在不同的圈上。

顯然，GT1是由b-圖或∞-圖粘貼樹(shù)而得到的圖。設(shè)GT1包含圈Ct+1=v1vl1vl2···vlt v1，則當(dāng)t ≥3 時(shí)，如果(X1+Xl2)2≥(Xn+Xl1)2，那么刪除邊vl1vl2和增加邊v1vl2，否則增加邊vnvl1可得圖︿G21。如果v1和vn是在圖的同一個(gè)圈上，那么可以使用情況2.1，否則繼續(xù)通過(guò)做一系列上述變換可得一個(gè)包含圈C3的圖。令vnvs1vs2···vskvn是圖︿G22的另一個(gè)圈，如果(X1+Xs1)2≥(Xn+Xs2)2，那么刪除邊vs1vs2和增加邊v1vs1，否則增加邊vnvs2可得圖。如果v1和vn在︿G23的同一個(gè)圈上，那么使用情況2.1，否則繼續(xù)通過(guò)做一系列上述變換可得圖是同構(gòu)于∞5、b7和b6中一個(gè)粘貼樹(shù)的圖。如果/∈H，那么通過(guò)對(duì)做一系列T2-變換得到的圖是同構(gòu)于圖1 的G4(p,q)、G5(p,q)和G6(p,q)中一個(gè)圖。

情況2.3v1和vn分別是在圈上和樹(shù)上。

不失一般性的假設(shè)v1在圈上和vn在樹(shù)上，則GT1包含圈Ct+1=v1vl1vl2···vltv1。當(dāng)t ≥3 時(shí)，如果(X1+Xl2)2≥(Xn+Xl1)2，那么刪除邊vl1vl2和增加邊v1vl2，否則增加邊vnvl1可得圖︿G31。如果v1和vn在圖︿G31的同一個(gè)圈上，那么可以使用情況2.1，否則繼續(xù)做一系列上述變換可得一個(gè)包含圈C3=v1vl1vl2v1的圖。設(shè)vs1vs2···vskvs1是的另一個(gè)圈，則如果(X1+Xs2)2≥(Xn+Xs1)2，那么刪除邊vs1vs2和增加邊v1vs2，否則增加邊vnvs1可得圖。如果v1和vn在中的圈上，那么可以使用情況2.1 或情況2.2，否則繼續(xù)通過(guò)做一系列上述變換得到的圖是θ4或∞5粘貼樹(shù)而得到的。如果/∈H，那么通過(guò)對(duì)做一系列T2-變換得到的圖是同構(gòu)于圖1 的G7(p,q),G8(p,q),···,G12(p,q)中一個(gè)圖。

情況2.4v1和vn在同一個(gè)樹(shù)上。

讓樹(shù)T粘貼在圈Ck中點(diǎn)vlm上，若令vt是v1和vn的共同鄰點(diǎn)，現(xiàn)在分兩種情況去討論。

情況2.4.1 假設(shè)存在路vnvtv1vl1vl2···vlm。

如果(X1+Xl2)2≥(Xn+Xl2)2，那么刪除邊vl1vl2和增加邊v1vl2，否則增加邊vnvl2，做一系列上述變換可得一個(gè)圈vl1vs2vs3···vskvl1。如果(X1+Xs2)2≥(Xn+Xs2)2，那么刪除邊vl1vs2和增加邊v1vs2，否則增加邊vnvs2可得圖。這時(shí)，在圖中，點(diǎn)v1在圈上和點(diǎn)vn在樹(shù)上，或點(diǎn)v1和vn在同一個(gè)圈上。如果前者成立，那么可以使用情況2.1，如果后者成立，那么可以使用情況2.3。

情況2.4.2 假設(shè)存在路v1vtvl1vl2···vlm。

如果(X1+Xl1)2≥(Xn+Xl1)2，那么刪除邊vtvl1和增加邊v1vl1，否則增加邊vnvl1可得圖。如果存在路vnvtv1vl1vl2···vlm，那么可以使用情況2.4.1，否則繼續(xù)做一系列上述變換可得圖vtvs2vs3···vskvt。如果(X1+Xl1)2≥(Xn+Xl1)2，那么刪除邊vtvl1和增加邊v1vl1，否則增加邊vnvl1可得圖。這時(shí)，在圖中，點(diǎn)v1和vn分別在圈上和樹(shù)上，則可以使用情況2.3。

根據(jù)以上分析可得，對(duì)于任意圖Gc ∈(n ≥12)，存在圖H ∈H′∪H′′，有

由于Q(Gc)=(n ?2)In+Jn ?Q(G)，其中Jn是一個(gè)所有元為1 的n階矩陣，所以使用方程(2)和(4)，可得

引理4如果H ∈H′′，那么存在圖H?∈H′，有λ(Hc)≥λ()。

證明 令X=(X1,X2,···,Xn)T是Hc的單位無(wú)符號(hào)拉普拉斯特征向量，其中X1≥X2≥··· ≥Xn，這時(shí)X1> 0 和Xn＜ 0。不失一般性的假設(shè)|Xn|≥|X1|，否則將X替換為?X。

對(duì)于圖Hi ∈H′′(i= 1,2)，在圖H′中可以刪除邊v1vn和增加邊vnvt得到的圖H?是同構(gòu)于G1(p,q)或G2(p,q)，所以

對(duì)于圖Hi ∈H′′(3≤i ≤7)，則刪除邊v1vn和增加邊vnvk得到的結(jié)果圖H?是同構(gòu)于G?(p,q)(?=2,6,7,8 或11)，所以

我們結(jié)合方程(2)、(5)和(6)，可得

引理5[10]令G是一個(gè)簡(jiǎn)單圖，則有λ(G)≤δ(G)，其中

引理6設(shè)p和q是兩個(gè)正整數(shù)，且p+q=n ?5(n ≥12)，則有

證明 不失一般性的假設(shè)p ≥q ≥1，需要求證

將以上方程轉(zhuǎn)換成矩陣方程(k1I7?Q1)X′=0，其中X′=(X1,X2,···,X7)T和令f1(x;p,q)=det(xI7?Q1)，則有

因此，有

引理7設(shè)p和q是滿足p+q=n ?5(n ≥12)的兩個(gè)正整數(shù)，則有λ((p,q))>λ((n ?5,0))。

證明 令X= (X1,X2,···,Xn)T是(p,q)的單位無(wú)符號(hào)拉普拉斯特征向量，若k2=λ(p,q))，則根據(jù)(p,q)的對(duì)稱性和無(wú)符號(hào)拉普拉斯特征方程(3)，可得

將以上方程轉(zhuǎn)換成矩陣方程(k2I7?Q2)X′=0，其中X′=(X1,X2,···,X7)T和

令f2(x;p,q)=det(xI7?Q2)，則有

因此，有

其中

引理9設(shè)p和q是兩個(gè)正整數(shù)，且有p+q=n ?7(n ≥12)，則有

證明 不失一般性的假設(shè)p ≥q ≥1。需要求證

將以上方程轉(zhuǎn)換成矩陣方程(k4I7?Q4)X′=0，其中X′=(X1,X2,···,X7)T和

令f4(x;p,q)=det(xI7?Q4)，則有

因此，有

其中

是正確的。

結(jié)合引理3、引理4 以及引理6 至引理10 中不等式，可得結(jié)論是正確的。

2 附錄

事實(shí)A設(shè)g1(x)是引理7 證明中的多項(xiàng)式，則當(dāng)0x ≤min{q+1,p+2}時(shí)，g1(x)>0。

證明 下面將對(duì)g1(x)進(jìn)行求導(dǎo)數(shù)，可得

設(shè)min{q+1,p+2}=p+2，則有0x ≤p+2。因?yàn)閜 ≥0 和n=p+q+5≥12，所以n ≥2p+6,q ≥4，因此

可得g1(x)是關(guān)于x的單調(diào)遞減多項(xiàng)式，所以

如果min{q+1,p+2}=q+1，那么0x ≤q+1，所以可得g1(x)>0。

事實(shí)B設(shè)g2(x)是引理9 證明中的多項(xiàng)式，則當(dāng)0x ≤q+3 時(shí)，g2(x)>0。

證明 下面對(duì)g2(x)進(jìn)行求導(dǎo)數(shù)，可得

因此g2(x)是關(guān)于x的單調(diào)遞減的多項(xiàng)式，所以

事實(shí)C設(shè)g4(x)是引理11 證明中的多項(xiàng)式，則當(dāng)0x ≤1 時(shí)，g4(x)>0。

證明 下面對(duì)g4(x)進(jìn)行求倒數(shù)，可得