圖變換及其在圖的最小無符號拉普拉斯特征值的應用

馮小蕓, 陳 旭, 王國平

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

0 引言

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

設G= (V(G),E(G))是一個連通簡單圖，可定義G的補圖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是一個雙圈圖。我們定義K1,n?1是帶有n個點的星圖，若K1,n?1+ 2e是從K1,n?1中連接兩對不同的懸掛點對而得到的圖，由于K1,n?1+2e的補圖(K1,n?1+2e)c含有一個孤立點，所以(K1,n?1+2e)c不連通。顯然，不少于12 個點的雙圈圖的補圖是非二部圖，所以我們僅考慮不少于12 個點的除了K1,n?1+2e(n ≥12)之外的雙圈圖的補圖。

Li 和Wang[10]確定除星圖K1,n?1的所有樹的補圖中最小無符號拉普拉斯特征值是最小的唯一圖。Yu 等[11]確定了除圖K1,n?1+e的所有單圈圖的補圖中最小無符號拉普拉斯特征值是最小的唯一圖。本文中，我們給出兩種圖變換，并且應用它們確定了帶有n ≥12 個點除了K1,n?1+2e的所有雙圈圖的補圖中最小無符號拉普拉斯特征值取最小的唯一圖。

1 主要結論

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

(2)式中的等號成立，當且僅當X是Q(G)的關于特征值λ(G)的特征向量。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

情況4v1和vn都在圖G的樹上。

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

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

其中NG(vi)是圖G中點vi的鄰域，方程(3)也被稱為圖G的無符號拉普拉斯特征方程。

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

令θ4和θ5分別是帶有4 個點和5 個點的θ-圖，令∞5和∞6分別是帶有5 個點和6 個點的∞-圖，令b6和b7分別是帶有6 個點和7 個點的b-圖，并且這些圖的兩個圈的長度都是3。

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

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

圖2 Hi(1 ≤i ≤7)

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

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

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

現在假設后者成立，則分兩種情況討論GT1。

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

情況1.1v1和vn在同一個帶有t+2 個點的圈Ct+2上。

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

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

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

情況1.3v1和vn分別在圈上和樹上。

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

情況1.4v1和vn在同一個樹T上。

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

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

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

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

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

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

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

情況2.3v1和vn分別是在圈上和樹上。

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

情況2.4v1和vn在同一個樹上。

讓樹T粘貼在圈Ck中點vlm上，若令vt是v1和vn的共同鄰點，現在分兩種情況去討論。

情況2.4.1 假設存在路vnvtv1vl1vl2···vlm。

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

情況2.4.2 假設存在路v1vtvl1vl2···vlm。

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

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

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

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

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

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

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

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

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

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

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

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

因此，有

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

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

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

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

因此，有

其中

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

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

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

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

因此，有

其中

是正確的。

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

2 附錄

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

證明 下面將對g1(x)進行求導數，可得

設min{q+1,p+2}=p+2，則有0x ≤p+2。因為p ≥0 和n=p+q+5≥12，所以n ≥2p+6,q ≥4，因此

可得g1(x)是關于x的單調遞減多項式，所以

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

事實B設g2(x)是引理9 證明中的多項式，則當0x ≤q+3 時，g2(x)>0。

證明 下面對g2(x)進行求導數，可得

因此g2(x)是關于x的單調遞減的多項式，所以

事實C設g4(x)是引理11 證明中的多項式，則當0x ≤1 時，g4(x)>0。

證明 下面對g4(x)進行求倒數，可得