一種特殊補(bǔ)圖的最小特征值

吳 翰，李 雨，孫 威，王振東，黃 星

(1.安慶師范大學(xué) 物理與電氣工程學(xué)院,安徽 安慶 246133;2.安慶師范大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 安慶 246133;3.安慶師范大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,安徽 安慶 246133)

·數(shù)學(xué)研究·

一種特殊補(bǔ)圖的最小特征值

吳 翰1，李 雨2，孫 威3，王振東1，黃 星1

(1.安慶師范大學(xué) 物理與電氣工程學(xué)院,安徽 安慶 246133;2.安慶師范大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 安慶 246133;3.安慶師范大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,安徽 安慶 246133)

鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣, 通常它的最小特征值就是圖的最小特征值. 本文針對(duì)一種特殊補(bǔ)圖的最小特征值, 刻畫了該類圖最小特征值達(dá)到極小的唯一圖.

鄰接矩陣；補(bǔ)圖；最小特征值

關(guān)于圖的譜半徑有不少的研究成果.然而，相對(duì)于譜半徑，最小特征值的研究較少.自范益政等人[10]在論文中刻畫了樹的補(bǔ)圖的最小特征值后，該研究引起了一些圖論學(xué)者的關(guān)注[11-15]，得到了一些成果，且所研究的圖的補(bǔ)圖均為連通圖.本文仍然從補(bǔ)圖的角度出發(fā)研究了給定階數(shù)的特殊補(bǔ)圖的最小特征值，并刻畫了此類圖最小特征值達(dá)極小的唯一圖.

下面我們引進(jìn)一些定義.設(shè)G=(V,E)為n階簡單圖，對(duì)于向量X∈Rn，如果存在一個(gè)從V到X中值的映射φ，使得對(duì)于任意u∈V有Xu=φ(u)，則稱X定義在G上.

我們發(fā)現(xiàn)對(duì)于任意向量X∈Rn，有

(1)

若λ是A(G)對(duì)應(yīng)于特征向量X的特征值，則由特征值的定義，當(dāng)且僅當(dāng)X≠0，對(duì)于每個(gè)v∈V，有

(2)

我們稱等式(2)為G關(guān)于X的特征等式.另外，對(duì)于任意單位向量X∈Rn，有

λmin(G)≤XTA(G)X,

(3)

當(dāng)且僅當(dāng)X是G的第一特征向量時(shí)等式成立.

Gc表示圖G的補(bǔ)圖.顯然有A(Gc)=J-I-A(G)，其中J,I分別表示n階全1矩陣和單位矩陣.因此，對(duì)于任意向量X∈Rn，有

XTA(G)X=XT(J-I)X-XTA(G)X.

(4)

記G(p,q)是階為p+q+2(p≥0,q≥1)的特殊圖，它是由兩個(gè)不相交的完全圖Kp,Kq以及兩個(gè)孤立點(diǎn)v4,v5通過以Kp的一個(gè)頂點(diǎn)v1與Kq的一個(gè)頂點(diǎn)v2為端點(diǎn)的邊v1v2和Kq的另一個(gè)頂點(diǎn)v3與兩個(gè)孤立點(diǎn)v4,v5為端點(diǎn)的邊v3v4，v3v5連接的圖.如圖1所示.特別地，當(dāng)q=1時(shí),v2=v3；當(dāng)p=0時(shí)，G(p,q)=G(0,q)為Kq的一個(gè)頂點(diǎn)v3與兩個(gè)孤立點(diǎn)v4,v5為端點(diǎn)的邊v3v4,v3v5連接的圖.

圖1 G(p,q)

引理1[16]設(shè)A是一個(gè)實(shí)對(duì)稱n×n階矩陣,B為A的m×m階主子陣,且λ1(A)≥λ2(A)≥…≥λn(A),λ1(B)≥λ2(B)≥…≥λm(B)分別為A與B的特征值,則對(duì)于i=1,2,…,m，有λn-m+i(A)≤λi(B)≤λi(A).

(5)

情形1：當(dāng)p=0時(shí).由等式(2)與(5)知Kq中除v3點(diǎn)外所有的點(diǎn)在X中對(duì)應(yīng)的值相同，記為X1，v4,v5點(diǎn)在X中對(duì)應(yīng)的值相同，記為X3.記Xv3=X2，記λmin(G(0,n-2)c)=λ，這樣由等式(2)可以得到

將上式轉(zhuǎn)換成矩陣等式(B-λI)X′=0,其中X′=(X1,X2,X3)T,

情形2：當(dāng)p=1時(shí).由等式(2)與(5)知Kq中除v2,v3兩點(diǎn)外所有的點(diǎn)在X中對(duì)應(yīng)的值相同，記為X1，v4,v5點(diǎn)在X中對(duì)應(yīng)的值相同，記為X5.記Xv1=X2,Xv2=X3,Xv3=X4，記λmin(G(1,n-3)c)=λ，再由等式(2)可以得到

將上式轉(zhuǎn)換成矩陣等式(B-λI)X′=0,其中X′=(X1,X2,X3,X4,X5)T,

令f2(x)=x4(1-x)+x3(3n-10)+x2(3n-16)-x(4n-18).

情形3：當(dāng)q=1時(shí).由等式(2)與(5)知，Kp中除v1點(diǎn)外所有的點(diǎn)在X中對(duì)應(yīng)的值相同，記為X1，v4,v5點(diǎn)在X中對(duì)應(yīng)的值相同，記為X4.記Xv1=X2,Xv2(v3)=X3,記λmin(G(n-3,1)c)=λ，這樣由等式(2)可以得到

將上式轉(zhuǎn)化成矩陣等式(B-λI)X′=0，其中X′=(X1,X2,X3,X4)T,

情形4：當(dāng)p,q≥2時(shí).由等式(2)與(5)可知Kp中除v1點(diǎn)外所有的點(diǎn)在X中對(duì)應(yīng)的值相同,記為X1,在Kq中除v2,v3兩點(diǎn)外所有的點(diǎn)在X中對(duì)應(yīng)的值相同，記為X4，v4,v5點(diǎn)在X中對(duì)應(yīng)的值相同，記為X6.記Xv1=X2,Xv2=X3,Xv3=X5,，記λmin(G(p,q)c)=λ，這樣由等式(2.2)可以知

將上式轉(zhuǎn)換成矩陣等式(B-λ1I)X′=0，其中X′=(X1,X2,X3,X4,X5,X6)T，

(1)若p≥q+2,當(dāng)x<-8時(shí)，我們有

>x2(x2(p-q-1)+x(3p-3q+1)-(3p-3q-1))

>x2(37(p-q)-71)>0.

(2)若q≥p+1,當(dāng)x<-8時(shí)，且q≥p+3時(shí)，我們有

>x2(x2(q-p-1)+x(3q-3p-7)-(3q-3p-5))

>x2(37(p-q)-3)>0.

當(dāng)x<-8時(shí)，且q=p+1時(shí)，我們有

當(dāng)x<-8時(shí)，且q=p+2時(shí)，我們有

再綜合情形1、2、3、4知結(jié)論成立.

[3]Y.Z.Fan，Y.Wang，Y.B.Gao.Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread[J].Linear Algebra Appl，2008(429).

[4]R.Liu，M.Zhai，J.Shu.The least eigenvalues of unicyclic graph with n vertices and k pendant vertices[J].Linear Algebra Appl，2009(431).

[6]Y.Y.Tan，Y.Z.Fan.The vertex(edge) independence number，vertex(edge) cover number and the least eigenvalue of a graph[J].Linear Algebra Appl，2010(433).

[7]Y.Wang，Y.Z.Fan.The least eigenvalue of a graph with cut vertices [J].Linear Algebra Appl，2010(433).

[8]M.L.Ye，Y.Z.Fan，D.Liang.The least eigenvalue of graphs with given connectivity[J].Linear Algebra Appl，2009(430).

[9] G.D.Yu，Y.Z.Fan，Yi Wang.Quadratic forms on graphs with application to minimizing the least eigenvalue of signless Laplacian over bicyclic graphs[J].Electronic Journal of Linear Algebra，2014(27).

[10]Y.Z.Fan，F(xiàn).F Zhang，Y.Wang.The least eigenvalue of the complements of tree [J].Linear Algebra Appl，2011(435).

[11]S.C.Li and S.J.Wang.The least eigenvalue of the signless Laplacian of the complements of trees[J].Linear Algebra Appl，2011(436).

[12]Y.Wang ，Y.Z.Fan，X.X.Li，et al.The least eigenvalue of graphs whosecomplements are unicyclic[J].Discussiones Mathematicae Graph Theory，2013,35(2).

[13]G.D .Yu，Y.Z.Fan.The least eigenvalue of graphs [J].Math.Res.Expo，2012(6).

[14]G.D.Yu ，Y.Z.Fan.The least eigenvalue of graphs whose complements are 2-vertex or 2-edge connected[J].Operations Research Transactions，2013(2).

[15]W.haemers.Interlacing eigenvalues and graphs[J].Linear Algebra Appl，1995(227-228).

2017-02-03

國家自然科學(xué)基金資助項(xiàng)目(11604002，51607004).

吳 翰(1993-)，男，安徽樅陽人，在讀碩士,研究方向?yàn)閳D形圖像處理.

O157.5

A

2095-185X(2017)02-0009-04