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

馮小蕓，陳 旭，王國平

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

迄今為止，連通圖的最小特征值已被廣泛研究，Xing等[1]在給定固定點數(shù)和懸掛點數(shù)的所有cacti圖中刻畫了具有最小特征值的唯一圖.Liu等[2]在具有固定懸掛點數(shù)的所有雙圈圖中給出了最小特征值達到最小值時的圖.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)}.近幾年，特殊圖類的補圖的最小特征值及相關(guān)問題引起了不少人的關(guān)注，Ren等[5]確定了一類θ圖的補圖的色等價類.Favaron等[6]得到了圖及其補圖的總控制權(quán)和總控制權(quán)細分數(shù).Ando等[7]討論了3連通圖的補圖的聯(lián)通度.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)對應(yīng)的一個特征向量，則任意的vi∈V(G)都有

(2)

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

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

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

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

前面提到λn(Gc)<-1，結(jié)合以上方程可以得到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的兩個非負整數(shù)，則有

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

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

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

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

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

3))成立.

將以上方程轉(zhuǎn)換成矩陣方程(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的兩個非負整數(shù)，則

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

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

將以上方程轉(zhuǎn)換成矩陣方程(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.

將以上方程轉(zhuǎn)換成矩陣方程(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.

現(xiàn)在首先計算

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

(7)

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

將以上方程轉(zhuǎn)換成矩陣方程(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)

將以上方程轉(zhuǎn)換成矩陣方程(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)進行如下求導(dǎo)，

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)進行如下求導(dǎo)，

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)進行如下求導(dǎo)，

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是一個正整數(shù)，有

當n≥28時，首先看到

還可知道

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

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

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 結(jié)論

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

1)當n是偶數(shù)時，

2)當n是奇數(shù)時，