具有n-4 个悬挂点的双圈补图的最小特征值的下界*

周恋恋，刘康，孟吉翔

（新疆大学数学与系统科学学院，新疆 乌鲁木齐 830017）

0 概念

本文研究的图均为简单且无向的连通图,图G=(V(G),E(G)) 是由点集V(G) 和边集E(G) 组成,其中V(G)={v1,v2,···,vn},E(G)={e1,e2,···,en}.补图Gc=(V(Gc),E(Gc)),其中V(Gc)=V(G),E(Gc)={vivj|vi,vj∈V(G),vivjE(G)}.图G的邻接矩阵为A(G)=(aij)n×n,当vi,vj相邻时,aij=1; 否则aij=0.实对称矩阵A(G) 所对应的特征值都是实数,记为λ1(G)≥λ2(G)≥···≥λn(G),最小特征值λn(G) 简记为λ(G),称其对应的特征向量为图G的第一特征向量.邻接矩阵的特征值及其重数的集合称为A-谱.设Bn,n-4为有n-4 个悬挂点的n阶双圈图集,则为其补图的集合.图的邻接矩阵的特征值是图谱理论的一个重要课题,其最小特征值的刻画得到了广泛研究.Johnsonc 等[1]在给定n个点和k条边的简单无向图中刻画了最小特征值达到最小的极图,Liu 等[2]确定了含有k个悬挂点的n阶单圈图的最小特征值达到最小的极图,Ye 等[3]在给定连通度的n阶图中得到了最小特征值达到最小的极图.随后学者们研究了补图的最小特征值,Fan 等[4]在所有树的补图中证明了最小特征值达到最小的极图; Jiang 等[5]在有两个悬挂点的图中刻画了连通补图最小特征值达到最小的极图.基于以上研究,本文在中刻画了最小邻接特征值的下界.关于其它图矩阵的谱方面的研究也有很多,具体可参阅文献[6-10].

1 预备知识

记图G的点集V(G)={v1,v2,···,vn},假设单位向量X=(Xv1,Xv2,···,Xvn)T使得Xvi=X(vi)(1≤i≤n),则

图G中与点v相邻的点的集合定义为v的邻域,记为NG(v),点v的度记为d(v)=|NG(v)|.假设X≠0 是G的特征值λ对应的特征向量,则对每个vi∈V有

称该式为特征等式.对于任意单位向量X∈Rn有

等式成立当且仅当X是G的第一特征向量.令Gc为图G的补图.由补图的定义有

其中J,I 分别表示n阶全1 矩阵和单位矩阵.

引理1[11]设A 是一个n×n阶实对称矩阵,B 是A 的m×m阶主子阵,且λ1(A)≥λ2(A)≥···≥λn(A),µ1(B)≥µ2(B)≥···≥µn(B) 分别为A 与B 的特征值,则对于i=1,2,···,m,有λn-m+i(A)≤µi(B)≤λi(A).

令图H是由两个C3共用一条边构成的双圈图,且V(H)={v1,v2,v3,v4},其中dH(v2)=dH(v4)=3.设p,q,r和s为任意非负整数,则图H6(p,q,r,s) 是通过在H的四个顶点v1,v2,v3,v4上分别粘p,q,r和s个悬挂点得到的双圈图,其中p+q+r+s=n-4.若p,q,r和s中有一个为0,则H中有三个点粘有悬挂点,由对称性不妨设r=0 或s=0,则产生的图分别记为H4(p,q,s) 和H5(p,q,r).若p,q,r和s中有两个为0,则H中有两个点粘有悬挂点,由对称性不妨设p=r=0,q=s=0 或r=s=0,此时产生的图分别记为H1(q,s),H2(p,r) 和H3(p,q) (见图1).

图1 有n-4 个悬挂点的双圈图

引理2设p,q,s为任意正整数且p+q+s=n-4.若n≥7,则存在图H∈{H1(q′,s′),H3(p′,q′)} 使得λ(Hc)≤λ(Hc4(p,q,s)),其中p′,q′和s′均为正整数.

证明设X是Hc4(p,q,s) 的第一特征向量,vji表示与vj(j=1,2,3,4) 相邻的悬挂点.由对称性知,与vj相邻的悬挂点的分量大小均相等.对H4(p,q,s) 中v1,v2,v4所对应特征向量分量的大小关系分以下2 种情形进行证明.

情形1Xv1≥Xv4≥Xv2(Xv2≥Xv4≥Xv1,Xv1≥Xv2≥Xv4或Xv4≥Xv2≥Xv1时类似).若与v4相邻的悬挂点对应的分量值大于等于零(即,Xv4i≥0,则Xv4iXv1≥Xv4iXv4≥Xv4iXv2),则删除该点带有的悬挂边连接点v1得H3(s+p,q),由(1) 得

XTA(Hc3(s+p,q))X-XTA(Hc4(p,q,s))X=2sXv4i(Xv4-Xv1)≤0,

即λ(Hc4(p,q,s))≥λ(Hc3(s+p,q)).若与v4相邻的悬挂点对应的分量值小于零(即,Xv4i＜0,则Xv4iXv1＜Xv4iXv4＜Xv4iXv2),则删除该点带有的悬挂边连接点v2得H3(p,s+q),由(1) 得

XTA(Hc3(p,s+q))X-XTA(Hc4(p,q,s))X=2sXv4i(Xv4-Xv2)≤0,

即λ(Hc4(p,q,s))≥λ(Hc3(p,s+q)).

情形2Xv2≥Xv1≥Xv4(Xv4≥Xv1≥Xv2时类似).若与v1相邻的悬挂点对应的分量值大于等于零(即,Xv1i≥0,则Xv1iXv2≥Xv1iXv1≥Xv1iXv4),则删除该点带有的悬挂边连接点v2得H1(p+q,s),由(1) 得

XTA(Hc1(p+q,s))X-XTA(Hc4(p,q,s))X=2pXv1i(Xv1-Xv2)≤0,

即λ(Hc4(p,q,s))≥λ(Hc1(p+q,s)).若与v1相邻的悬挂点对应的分量值小于零(即,Xv1i＜0,则Xv1iXv2＜Xv1iXv1＜Xv1iXv4),则删除该点带有的悬挂边连接点v4得H1(q,s+p).由(1) 得

XTA(Hc1(q,s+p))X-XTA(Hc4(p,q,s))X=2pXv1i(Xv1-Xv4)≤0,

即λ(Hc4(p,q,s))≥λ(Hc1(q,s+p)).

引理3设p,q,r为任意正整数且p+q+r=n-4.若n≥7,则存在图H∈{H2(p′,r′),H3(p′,q′)} 使得λ(Hc)≤λ(Hc5(p,q,r)),其中p′,q′和r′均为正整数.

与引理2 的证明类似,可得引理3 成立.

引理4设p,q,r和s为任意正整数且p+q+r+s=n-4.若n≥8,则存在图H∈{H4(p′,q′,s′),H5(p′,q′,r′)} 使得λ(Hc)≤λ(Hc6(p,q,r,s)),其中p′,q′,r′和s′均为正整数.

证明设X是Hc6(p,q,r,s) 的第一特征向量.设vji表示与vj(j=1,2,3,4) 相邻的悬挂点.由对称性知,与vj相邻的悬挂点的分量大小均相等.不妨设Xv1≥Xv3,对H6(p,q,r,s) 中v1,v2,v3,v4所对应特征向量分量的大小关系分以下2 种情形进行证明.

情形1Xv2≥Xv1≥Xv3≥Xv4(Xv1≥Xv2≥Xv3≥Xv4,Xv1≥Xv4≥Xv3≥Xv2,Xv2≥Xv4≥Xv1≥Xv3,Xv4≥Xv1≥Xv3≥Xv2或Xv4≥Xv2≥Xv1≥Xv3时类似).由对称性不妨考虑v3.若与v3相邻的悬挂点对应的分量值大于等于零(即,Xv3i≥0,则Xv3iXv2≥Xv3iXv3≥Xv3iXv4),则删除该点带有的悬挂边连接点v2得H4(p,r+q,s),由(1) 得

XTA(Hc4(p,r+q,s))X-XTA(Hc6(p,q,r,s))X=2rXv3i(Xv3-Xv2)≤0,

即λ(Hc6(p,q,r,s))≥λ(Hc4(p,r+q,s)).若与v3相邻的悬挂点对应的分量值小于零(即,Xv3i＜0,则Xv3iXv1＜Xv3iXv3＜Xv3iXv4),则删除该点带有的悬挂边连接点v4得H4(p,q,s+r),由(1) 得

XTA(Hc4(p,q,s+r))X-XTA(Hc6(p,q,r,s))X=2rXv3i(Xv3-Xv4)≤0;

即λ(Hc6(p,q,r,s))≥λ(Hc4(p,q,s+r)).

情形2Xv1≥Xv3≥Xv2≥Xv4(Xv1≥Xv2≥Xv4≥Xv3,Xv1≥Xv3≥Xv2≥Xv4,Xv1≥Xv3≥Xv4≥Xv2,Xv1≥Xv4≥Xv2≥Xv3,Xv4≥Xv1≥Xv2≥Xv3或Xv2≥Xv1≥Xv4≥Xv3时类似).分析得,分量的大小顺序排在第二位的点v3与情形1 得到的结果相同,则考虑排在第三位的点v2.若与v2相邻的悬挂点对应的分量值大于等于零(即,Xv2i≥0,则Xv2iXv1≥Xv2iXv2≥Xv2iXv4),则删除该点带有的悬挂边连接点v1得H5(p+q,r,s),由(1) 得

XTA(Hc5(p+q,r,s))X-XTA(Hc6(p,q,r,s))X=2qXv2i(Xv2-Xv1)≤0,

即λ(Hc6(p,q,r,s))≥λ(Hc5(p+q,r,s)).若与v2相邻的悬挂点对应的分量值小于零(即,Xv2i＜0,则Xv2iXv1＜Xv2iXv2＜Xv2iXv4),则删除该点带有的悬挂边连接点v4得H5(p,r,s+q),由(1) 得

XTA(Hc5(p,r,s+q))X-XTA(Hc6(p,q,r,s))X=2qXv2i(Xv2-Xv4)≤0,

即λ(Hc6(p,q,r,s))≥λ(Hc5(p,r,s+q)).

由引理2、引理3、引理4,接下来主要考虑H1(q,s),H2(p,r),H3(p,q) 三类图.

引理5给定正整数n(n≥8),假设q,s为任意正整数且q+s=n-4.当q＞s≥1 时,有λ(Hc1(q,s))＞λ(Hc1(q-1,s+1)).

证明假设X是Hc1(q,s)的第一特征向量.由于K2,2⊂Hc1(q,s)且λ(K2,2)=-2,由引理1 可得λ(Hc1(q,s))≤-2.由对称性得,v2和v4分别悬挂的q和s个悬挂点分量大小相同,分别记为X5和X6,记Xvi=Xi(i=1,2,3,4).由(2) 可得:

上式可写为矩阵等式(λE-B)X′=0,其中

令PHc1(q,s)=(x+1)n-6f(x;q,s),其中f(x;q,s)=det(λE-B),则f(x;q,s)=x6+(2-q-s)x5+(-4q-4s)x4+(-2-4q-4s+2qs)x3+(5qs-1)x2+(q+s+2qs)x-qs.其中,λ是f(x;q,s)=0 的最小根.f(x;q-1,s+1)-f(x;q,s)=(q-s-1)(x+1)(x(2x+3)-1).由于q-s-1＞0,又λ≤-2,则f(x;q-1,s+1)-f(x;q,s)=(q-s-1)(x+1)(x(2x+3)-1)＜0.当n为偶数时,PHc1(q-1,s+1)-PHc1(q,s)＜0,当n为奇数时,PHc1(q-1,s+1)-PHc1(q,s)＞0,则有λ(Hc1(q,s))＞λ(Hc1(q-1,s+1)).

由引理5,推论1 显然成立.

推论1设q,s为任意正整数且q+s=n-4.若n≥8,则λ(Hc1(q,s))≥λ(Hc1(「(n-4)/2」,「(n-4)/2」)),等号成立当且仅当H1(q,s)=H1(「(n-4)/2」,「(n-4)/2」).

引理6给定正整数n(n＞10),假设p,r为任意整数且p+r=n-4.当p＞r≥0 时,有λ(Hc2(p,r))＞λ(Hc2(p-1,r+1)).

证明假设X是H2c(p,r) 的第一特征向量.若r＞0,由于K2,3⊂H2c(p,r) 且由引理1 可得由对称性得,v1和v3分别悬挂的p和r个悬挂点分量大小相同,分别记为X5和X6,记Xvi=Xi(i=1,2,3,4).由(2) 可得:

上式可写为矩阵等式(λE-B)X′=0,其中

令PHc2(p,r)=(x+1)n-6f(x;p,r),其中f(x;p,r)=det(λE-B),则f(x;p,r)=x6+(2-p-r)x5+(-4p-4r)x4+(-2-2p-2r+2pr)x3+(-1+3p+3r+3pr)x2+(2p+2r-4pr)x.其中,λ是f(x;p,r)=0 的最小根.f(x;p-1,r+1)-f(x;p,r)=(p-r-1)x(2x2+3x-4).由于p-r-1＞0,又则f(x;p-1,r+1)-f(x;p,r)=(p-r-1)x(2x2+3x-4)＞0.当n为偶数时,PHc2(p-1,r+1)-PHc2(p,r)＜0,当n为奇数时,PHc2(p-1,r+1)-PHc2(p,r)＞0,则有λ(Hc2(p,r))＞λ(Hc2(p-1,r+1)).

若r=0,此时

将上式转换成矩阵等式(λE-B)X′=0,其中p+r=n-4,则

由引理6,推论2 显然成立.

推论2 设p,r为任意正整数且p+r=n-4.若n＞10,则λ(Hc2(p,r))≥λ(Hc2(「(n-4)/2」,「(n-4)/2」)),等号成立当且仅当H2(p,r)=H2(「(n-4)/2」,「(n-4)/2」).

引理7假设p,q为任意正整数且p+q=n-4.当p＞q≥0 时,则有以下结论:

(i)若n≥13 为奇数,则λ(Hc3(p,q))≥λ(Hc3((n-1)/2,(n-7)/2)),等号成立当且仅当p=(n-1)/2,q=(n-7)/2;

(ii)若n≥18 为偶数,则λ(Hc3(p,q))≥λ(Hc3((n-2)/2,(n-6)/2)),等号成立当且仅当p=(n-2)/2,q=(n-6)/2.

证明注意到p+q=n-4,对于p,q为任意非负整数,令=(x+1)n-6f(x;p,q),其中f(x;p,q)=det(λE-B).

(i) 当n为奇数时,-=(x+1)n-6(f(x;(p+q+3)/2,(p+q-3)/2)-f(x;p,q)).f(Hc3(p+q+3)/2,(p+q-3)/2)(-2.8)＜0,则λ(Hc3(p+q+3)/2,(p+q-3)/2)＜-2.8.下证当x≤-2.8 时,f(x;(p+q+3)/2,(p+q-3)/2-f(x;p,q))=1/4(p-q-3)(2(p-q+1)x3+(5p-5q+9)x2+(p-q+1)x-p+q-3)≤0.易知,1/4(p-q-3)≥0,则需证当x≤-2.8 时,y(x)=2(p-q+1)x3+(5p-5q+9)x2+(p-q+1)x-p+q-3＜0,而y′(x)=6(p-q+1)x2+2(5p-5q+9)x+p-q+1.其对称轴x=-5/6-2/(3(1+p-q))＞-2.8,且y′(-2.8)=-2.36+20.04(p-q)＞0,则当x≤-2.8 时,y(x)单调递增,而y(-2.8)=20.856-8.504(p-q)＜0.则可得y(x)＜0.由于p-q＞0 且存在p-q=3,则-≥0.

(ii) 当n为偶数时,-=(x+1)n-6(f(x;(p+q+2)/2,(p+q-2)/2)-f(x;p,q)).f(Hc3((p+q+2)/2,(p+q-2)/2))(-3.3)＜0,则λ(Hc3((p+q+2)/2,(p+q-2)/2))＜-3.3.下证当x≤-3.3 时,f(x;(p+q+2)/2,(p+q-2)/2)-f(x;p,q)=1/4(p-q-2)(2(p-q)x3+(5p-5q+4)x2+(p-q)x-p+q-2)≤0.易知,1/4(p-q-2)≥0,则需证当x≤-3.3 时,y(x)=2(p-q)x3+(5p-5q+4)x2+(p-q)x-p+q-2＜0,而y′(x)=6(p-q)x2+2(5p-5q+4)x+p-q.其对称轴x=-5/6-(2/3)(p-q)＞-3.3,且y′(-3.3)=-26.4+33.34(p-q)＞0,则当x≤-3.3 时,y(x) 单调递增,而y(-3.3)=41.56-21.724(p-q)＜0.则可得y(x)＜0.由于p-q＞0 且存在p-q=3,则-≤0.

引理8若n≥14,则λ(Hc2(「(n-4)/2」,「(n-4)/2」))＜λ(Hc1(「(n-4)/2」,「(n-4)/2」)).

证明注意到

引理9若n≥13 为奇数,则λ(Hc2((n-3)/2,(n-5)/2))＜λ(Hc3((n-1)/2,(n-7)/2)); 若n≥18 为偶数,则λ(Hc2((n-4)/2,(n-4)/2))＜λ(Hc3((n-4)/2,(n-6)/2)).

证明由推论2,引理7 和式(5) 得,若n≥13 且n为奇数,-=(x+1)n-6(f(Hc2((n-3)/2,(n-5)/2))-f(Hc3((n-1)/2,(n-7)/2)))=(x+1)n-6(n-3)x3-(1/2)((n-11)n+16)x2+下证当x≤-2.8 时,y(x)=(n-3)x3-(1/2)((n-11)n+16)x2+(1/4)((42-5n)n-81)x+(1/4)((n-8)n+7)＜0.y′(x)=3(n-3)x2-((n-11)n+16)x+(1/4)((42-5n)n-81),对称轴x=[(n-11)n+16]/12(n-3)＞-2.8,当n≥5 时,y′(-2.8)=1.55n2+3.22n-46.01＞0,则当x≤-2.8 时,y(x)单调递增,y(-2.8)=-0.17n2-10.232n+61.586＜0.则可得y(x)＜0,从而＞若n≥6 且n为偶数,则当p+q≥18 时,-=(x+1)n-6f(Hc2((n-4)/2,(n-4)/2))-下证当x≤-3.3 时,y(x)=(n-4)x3-(1/2)(n-8)(n-3)x2+(1/4)((42-5n)n-88)x+(1/4)((n-8)n+12)＜0.y′(x)=3(n-4)x2-(n-8)(n-3)x+(1/4)((42-5n)n-88),对称轴x=[(n-8)(n-3)]/6(n-4)＞-3.3,当n≥6 时,y′(-3.3)=2.05n2+6.87n-73.48＞0,则当x≤-3.3 时,y(x)单调递增,而y(-3.3)=-1.07n2-12.692n+88.668＜0,则可得y(x)＜0,从而＜.

设Hc∈.当6≤n≤18 时,通过MATLAB 编程可知λ(Hc)≤λ(H2c(「(n-4)/2」,「(n-4)/2」)).当n≥19 时,由引理8 和引理9 知λ(Hc)≤λ(Hc2(「(n-4)/2」,「(n-4)/2」)).当n=6 时,λ(Hc2(1,1))=-2≥当n=7 时,所以,当n=7 时,因此本文接下来只需考虑n≥8 时的下界.

定理1当n≥8 时,对任意的Hc∈有

证明当n≥6 且n为偶数时,由式(5) 知令

当n≥9 且n为奇数时,由式(5) 知令

当n≥9 时,分别讨论h(-2.4)和h(-1)与0 的关系.注意到设h(-2.4)=0.32n2+19.033 6n-171.138 56.因为h′(-2.4)=0.64n+19.033 6＞0,则n≥9 时h(-2.4) 为增函数且h(-2.4)＞h(-2.4) |n=9≈26.083 84＞0.设h(-1)=-5n2+40n-75.因为h′(-1)=-10n+40＜0,则n≥9 时h(-1) 为减函数且h(-1)＜h(-1)|n=9=-120＜0.

当n≥11 时,分别讨论h(0.851),h(n-3)和h(n-2)与0 的关系.设h(0.851)=0.001 402n2+0.448 59n-5.034 77,因为h′(0.851)=0.002 804n+0.448 59＞0,则n≥9 时h(0.851)为增函数且h(0.851)＞h(0.851)|n=11=0.069 362＞0.设h(n-3)=-2n4+31n3-169n2+393n-341,h′(n-3)=-8n3+93n2-338n+393,h′′(n-3)=-24n2+186n-338以及h′′′(n-3)=-48n+186＜0.从而h′′(n-3) 单调递减且h′′(n-3)＜h′′(n-3)|n=11=-1 196＜0,则h′(n-3)单调递减且h′(n-3)＜h′(n-3)|n=11=-2 720＜0,则h(n-3) 单调递减且h(n-3)＜h(n-3)|n=11=-4 488＜0.设h(n-2)=2n4+3n3-56n2+129n-118＞0,h′(n-2)=8n3+9n2-112n+129,h′′(n-2)=24n2+18n-112 以及h′′′(n-2)=48n+18＞0.从而h′′(n-2) 单调递增且h′′(n-2)＞h′′(n-2)|n=11=2 984＞0,则h′(n-2) 单调递增且h′(n-2)＞h′(n-2)|n=11=10 568＞0,则h(n-2) 单调递增且h(n-2)＞h(n-2)|n=11=27 800＞0.注意到当n=9 时,则

综上所述,当n≥8 时,对任意的Hc∈有