具有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∈有