仅有三个悬挂点的图的补图的最小特征值

冯小芸，陈 旭，王国平

(新疆师范大学数学科学学院，乌鲁木齐 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是奇数时，