僅有三個懸掛點的圖的補圖的最小特征值

馮小蕓，陳 旭，王國平

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

迄今為止，連通圖的最小特征值已被廣泛研究，Xing等[1]在給定固定點數和懸掛點數的所有cacti圖中刻畫了具有最小特征值的唯一圖.Liu等[2]在具有固定懸掛點數的所有雙圈圖中給出了最小特征值達到最小值時的圖.Wang等[3]在帶有割邊的所有圖中，確定了最小特征值達到最小值時的圖.Liu等[4]確定了含有k個懸掛點的n個點的單圈圖的最小特征值.

圖G=(V(G)，E(G))的補圖記為Gc=(V(Gc)，E(Gc))，其中V(Gc)=V(G)且E(Gc)={xy：x，y∈V(G)，xy?E(G)}.近幾年，特殊圖類的補圖的最小特征值及相關問題引起了不少人的關注，Ren等[5]確定了一類θ圖的補圖的色等價類.Favaron等[6]得到了圖及其補圖的總控制權和總控制權細分數.Ando等[7]討論了3連通圖的補圖的聯通度.Fan等[8]給出了所有樹的補圖中最小特征值達到極小時的連通圖，Jiang等[9]得到了恰有兩個懸掛點的圖的所有連通補圖的最小特征值.

本文在僅有三個懸掛點的圖的所有連通補圖中，確定了其最小特征值達到最小值時的唯一圖.

1 主要引理及證明

假定G是點集為V(G)={v1，v2，…，vn}的一個圖，且令X=(Xv1，Xv2，…，Xvn)T是使得Xvi=X(vi)(1≤i≤n)的一個單位向量，因此，

(1)

若X≠0是與G的特征值λ(G)對應的一個特征向量，則任意的vi∈V(G)都有

(2)

其中，NG(vi)是點Vi的鄰域，等式(2)稱為G的特征方程.

令Kn是n個點的完全圖，若G是至少含有一條邊的連通圖，則K2是G的一個誘導子圖，已知λn(K2)=-1，由交錯定理知λn(G)≤-1.

再次，通過特征方程(2)，有

通過以上方程和特征方程(2)，對任意的v′∈NG(u){w}，得到

前面提到λn(Gc)<-1，結合以上方程可以得到Xv′=Xw>0，該矛盾表明X至少包含兩個正分量.由于-X也是Gc的最小特征向量，因此可以類似地驗證X至少包含兩個負分量.

(3)

將Jn和In分別記為n階的全一矩陣和單位矩陣.通過式(1)，(3)和Rayleigh定理，得到

λn(Gc)=XTA(Gc)X=

XT(Jn-In)X-XTA(G)X>

XT(Jn-In)X-XTA(G(p，q；s，t))X=

XTA(Gc(p，q；s，t))X≥

λn(Gc(p，q；s，t)).

接下來為了表達方便，把G(0，3；s，t)寫為G1(s，t)(s=0或s≥3)，且將G(1，2；s，t)記為G2(s，t).

引理3令s和t是滿足s+t=n-3≥25的兩個非負整數，則有

證明圖G1(s，t)如圖1所示.

圖1 G1(s，t)Fig.1 G1(s，t)

將以上方程轉換成矩陣方程(k1I3-A1)X′=0，其中X′=(Xv2，Xt，Xv3)T且

令φ1(x)=det(xI3-A1)，則φ1(x)=x3-2x2-(3n-12)x.由φ1(k1)=0，可得

將以上方程轉換成矩陣方程(k2I4-A2)X′=0，其中X′=(Xs，Xu1，Xv1，Xv3)T且

3))成立.

將以上方程轉換成矩陣方程(k3I6-A3)X′=0，其中X′=(Xs，Xu1，Xv1，Xt，Xv2，Xv3)T且

令f(x；s，t)=det(xI6-A3)，則

f(x；s，t)=x6-2x5+
(-st-3s-3t+4)x4+
(-4st+6s+4)x3+(4st-s+2t-8)x2+
(4st-10s-4t+10)x-3st+6s+3t-6.

因為3≤s≤n-5，所以st=s(n-3-s)≥3(n-5)，因此

f(-8；s，t)=-1827st-15338s-12125t+
341418≤-20819n+414837+3213t<0，

這意味著k3<-8.

下面分成兩種情況進行討論.

情況1s≥t+2.

首先有

f(x；s，t)-f(x；s-1，t+1)=

(x-1)(x+1)g(x)，

(4)

其中，

g(x)=(s-t-1)x2+(4s-4t+2)x-3s+3t.

情況2t≥s+1.

首先得到

f(x；s，t)-f(x；s+1，t-1)=

-(x-1)(x+1)g(x)，

(5)

其中，g(x)=(s-t+1)x2+(4s-4t+10)x-3s+3t-6.

最后，來驗證

首先有

x2φ2(x)-f(x；n-5，2)=x(n-6)h(x)，

(6)

其中，h(x)=x3+4x2-4x+2.

通過以上討論，可確定

引理4讓s和t是滿足s+t=n-3≥23的兩個非負整數，則

證明讓圖G2(s，t)如圖2所示.

圖2 G2(s，t)Fig.2 G2(s，t)

將以上方程轉換成矩陣方程(t1I5-B1)X′=0，其中X′=(Xs，Xu1，Xu2，Xu3，Xv3)T且

令ψ1(x)=det(xI5-B1)，則ψ1(x)=x5-x4-(3n-10)x3-(3n-16)x2-(-4n+18)x.

將以上方程轉換成矩陣方程(t2I6-B2)X′=0，其中X′=(Xs，Xu1，Xu2，Xu3，Xv1，Xv3)T且

令ψ2(x)=det(xI6-B2)，則

ψ2(x)=x6-x5+(-4n+15)x4+

(-4n+23)x3+(8n-41)x2+

(2n-13)x-2n+12.

現在首先計算

xψ1(x)-ψ2(x)=(x+1)g(x)，

(7)

其中，g(x)=(n-5)x3-2x2+(-4n+25)x+2n-12.

將以上方程轉換成矩陣方程(t3I6-B3)X′=0，其中X′=(Xs，Xu1，Xv1，Xt，Xu2，Xu3)T且

令ψ3(x)=det(xI6-B3)，則

ψ3(x)=x6-x5+(-4n+15)x4+

(35-6n)x3+(7n-35)x2+

(3n-19)x-2n+12.

首先有

ψ3(x)-ψ2(x)=-(n-6)x(x+1)(2x-1)，

(8)

將以上方程轉換成矩陣方程(t4I8-B4)X′=0，其中X′=(Xs，Xu1，Xu2，Xu3，Xv1，Xt，Xv2，Xv3)T且

令F(x；s，t)=det(xI8-B4)，則

F(x；s，t)=x8-x7+(-st-3s-3t+2)x6+
(-5st+s-t+12)x5+(8s+7t-14)x4+
(12st-14s-11t+6)x3+
(-st-5s-4t+20)x2+
(-7st+15s+14t-30)x+2st-4s-4t+8.

由于2≤s≤n-5，則st=s(n-3-s)≥2(n-5)，因此F(-7；s，t)=-37728st-346098s-315858t+6587484≤-30240s-391314n+7912338<0，這表明t4<-7.

下面分成兩種情況來討論.

情況1s≥t+2．

首先得到

F(x；s，t)-F(x；s-1，t+1)=

(x-1)(x+1)g(x)，

(9)

其中，g(x)=(s-t-1)x4+(5s-5t-3)x3+(s-t)x2+(-7s+7t+6)x+2s-2t-2.

對g(x)進行如下求導，

g′(x)=4(s-t-1)x3+3(5s-5t-3)x2+

(2(s-t))x-7s+7t+6，

g″(x)=12(s-t-1)x2+6(5s-5t-3)x+

2s-2t，

g?(x)=24(s-t-1)x+30s-30t-18.

情況2t≥s+1．

首先得到

F(x；s，t)-F(x；s+1，t-1)=

-(x-1)(x+1)g(x)，

(10)

其中，g(x)=(s-t+1)x4+(5s-5t+7)x3+(s-t+2)x2+(-7s+7t-8)x+2s-2t+2.

對g(x)進行如下求導，

g′(x)=4(s-t+1)x3+[3(5s-5t+7)]x2+

[2(s-t+2)]x-7s+7t-8，

g″(x)=12(s-t+1)x2+[6(5s-5t+7)]x+

2s-2t+4，

g?(x)=24(s-t+1)x+30s-30t+42.

接下來驗證

首先有

x2ψ2(x)-F(x；n-5，2)=xh(x)，

(11)

其中，h(x)=(n-6)x5+(5n-32)x4+(5n-35)x-x3+(-8n+53)x2-n+7.

對h(x)進行如下求導，

h′(x)=4(5n-32)x3+5(n-6)x4+5n-

35-3x2+2(-8n+53)x，

h″(x)=12(5n-32)x2+20(n-6)x3-

6x-16n+106，

h?(x)=24(5n-32)x+60(n-6)x2-6，

h(4)(x)=120n-768+120(n-6)x.

通過以上討論，最終確定出

引理5令n≥28是一個正整數，有

當n≥28時，首先看到

還可知道

其中，h(x)=2x4+(4n-22)x3+(n2-10n+22)x2+(-4n+30)x-n2+14n-48.

對h(x)進行如下求導，

h′(x)=8x3+3(4n-22)x2+

2(n2-10n+22)x-4n+30，

h″(x)=24x2+6(4n-22)x+2n2-20n+44=

(x-x1)(x-x2)，

其中,

令

當n≥28時，有

可以計算出

(2x2+(n-7)x-n+7)(2x2+(n-3)x+n-7)=

這表明

2 結論

結合引理2，引理3，引理4和引理5，得到以下主要結論.

1)當n是偶數時，

2)當n是奇數時，