一種特殊補圖的最小特征值研究

李 雨，薛婷婷，孫 威，王振東，黃 星

(安慶師范大學，安徽 安慶 246133)

?

一種特殊補圖的最小特征值研究

李 雨，薛婷婷，孫 威，王振東，黃 星*

(安慶師范大學，安徽 安慶 246133)

圖的鄰接矩陣是表示頂點之間相鄰關系的矩陣,它的最小特征值就是圖的最小特征值。討論特殊補圖的最小特征值,并刻畫此類圖最小特征值達極小的唯一圖，也是有意義的。

圖論；鄰接矩陣；補圖；最小特征值

設G=(V,E)是一個頂點集為V={v1,v2,…,vn}和邊集為E={e1,e2,…,en}的n階簡單圖,頂點v∈V的鄰域定義為NG(v)={u∶uv∈E},頂點v∈V的度定義為d(v)=|NG(v)|。若|NG(v)|=1，則稱v為G的懸掛點。如果圖G中任意兩點間均有一條路連接，則稱G是連通的。圖G的鄰接矩陣定義為A(G)=(aij)n×n，其中，當vi與vj相鄰時，aij=1，否則aij=0。A(G)的特征值被稱為圖G的特征值。由于A(G)是實對稱矩陣，故其特征值為實數，可以進行排序，我們稱A(G)的最小特征值為圖G的最小特征值，記為λmin(G)。

鄰接譜半徑的極圖問題是譜圖理論的熱點問題。然而,相對于譜半徑,最小特征值研究很少被人注意到。2008年，Bell在文獻[1,2]中刻畫了某些圖類的最小特征值的極小圖。他的工作使得圖的最小特征值問題受到國內外學者的注意，具體可參閱文獻[3-15]。特別是文獻[11-15]，都是從補圖的結構出發，研究了原圖的最小特征值。本文仍然從補圖的角度出發研究給定階數的特殊補圖的最小特征值，并刻畫此類圖最小特征值達極小的唯一圖。

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

我們發現對于任意向量X∈Rn，有

(1)

若λ是A(G)對應于特征向量X的特征值,則由特征值的定義,當且僅當X≠0,對于每個v∈V,有

(2)

我們稱等式(2)為G關于X的特征等式。另外,對于任意單位向量X∈Rn,有

λmin(G)≤XTA(G)X

(3)

當且僅當X是G的第一特征向量時等式成立。

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

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

(4)

記H2(p,q)(如圖1所示)是階為p+q+2(p≥1,q≥1)的特殊圖，它是由兩個不相交的完全圖Kp,Kq以及兩個孤立點v4,v6通過以Kp的一個頂點v1與Kq的一個頂點v2為端點的邊v1v2和Kp,Kq各一個頂點v3,v5與兩個孤立點v4,v6為端點的邊v3v4，v5v6連接的圖。特別地，當q=1時,v2=v5；當p=1時,v1=v3。

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

定理2 給定一個正整數n(n≥11),對于任意的整數p≥1,q≥1且p+q=n-2,我們有λmin(H2(p,q)c)≥λmin(H2([n-2/2],[n-2/2])c),當且僅當p=[n-2/2],q=[n-2/2]時等號成立。

證明 設H2(p,q)如圖1所示,由于K2?H2(p,q)c,λmin(k2)=-1。由引理1可知

λmin(H2(q,p)c)≤-1

(5)

設X是H2(p,q)c的第一特征向量。

情形1：當p=1時。由等式(2)與(5)知Kq中除v2,v5兩點外所有的點在X中對應的值相同，記為X1。記Xv1(v3)=X2,Xv2=X3,Xv4=X4Xv5=X5,Xv6=X6,記λmin(H2(1,n-3)c)=λ，這樣由等式(2)可以得到,

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

令

f1(x)=det(B-xI)=x6-x4(3n-9)-x3(4n-18)+x2(4n-16)+2x(n-5)-(n-5)。

情形2：當q=1時。由等式(2)與(5)知Kp中除v1,v3兩點外所有的點在X中對應的值相同,記為X1。記Xv1=X2,Xv2(v5)=X3,Xv3=X4,Xv4=X5,Xv6=X6,記λmin(H2(n-3,1)c)=λ,再由等式(2)可以得到,

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

令

f2(x)=det(B-xI)=x6-x4(3n-9)-x3(4n-18)+x2(4n-16)+2x(n-5)-(n-5)。

情形3：當p,q≥2時。由等式(2)與(5)可知Kp中除v1,v3點外所有的點在X中對應的值相同,記為X1,在Kq中除v2,v5兩點外所有的點在X中對應的值相同,記為X4記Xv1=X2,Xv2=X3,Xv3=X5,Xv4=X6,Xv5=X7,Xv6=X8,λmin(H2(p,q)c)=λ,這樣由等式(2)可以知,

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

令

f(x；p,q)=det(B-xI)=x8-x6(pq+2n-6)-x5(4pq-8)+x4(4n-15)+x3(8pq-8n+20)-x2(3n-17)-4x(pq-2n+8)+(pq-2n+8)。

由于2≤x≤n-4時，φ(x)=x(n-2-x)取最小值φ(2)=2(n-4)，故當p,q≥2,p+q=n-2時，pq=p(n-2-p)≥2(n-4)。則當p,q≥2且p+q=n-2≥9時，f(-4;p,q)=77208-6738n-495pq<0，從而有λ<-4。

(1)若p≥q+2,當x<-4時，我們有

f(x;p,q)-f(x,p-1,q+1)=(p-q-1)(x6+4x5-8x3+4x-1)>0。

由于λ是方程f(x;p,q)的最小根,從而有f(λ;p,q)=0,這樣由上式可得到f(λ;p-1,q+1)<0,這意味著

λmin(H2(p,q)c)>λmin(H2(p-1,q+1)c)>…>λmin(H2([n-2/2],[n-2/2])c)。

(2)若q≥p+1,當x<-4時，且q≥p+2時，我們有

f(x;p,q)-f(x;p+1,q-1)=(q-p-1)(x6+4x5-8x3+4x-1)>0。

當x<-8時，且q=p+1時，我們有

f(x;p,q)-f(x;p+1,q-1)=0。

由于λ是方程f(x;p,q)的最小根,從而有f(λ;p,q)=0,則由上面的討論知當q≥p+1時，我們有f(λ;p+1,q-1)≤0,這意味著

λmin(H2(p,q)c)≥λmin(H2(p+1,q-1)c)≥…≥λmin(H2([n-2/2],[n-2/2])c)。

下面比較λmin(H2(n-4,2)c)與λmin(H2(n-3,1)c)的大小。

因為n≥11且x<-4，有x2f2(x)-f(x;n-4,2)=x6(n-5)+x5(4n-22)-x4-x3(6n-34)+x2(2n-12)>x6(n-5)+x5(4n-22)-x4=φ(x)關于x單調遞減，故有x2f3(x)-f(x;n-4,2)>φ(-4)=7x4>0。因為λmin(H2(n-4,2)c)<-4，我們有λmin(H2(n-4,2)c)<λmin(H2(n-3,1)c)。

再綜合情形1、2、3知結論成立。

[4] 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(2-3):577-588.

[5] 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(5-7):657-665.

[7] 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(4):790-795.

[8] Y.Wang,Y.Z.Fan.The least eigenvalue of a graph with cut vertices[J].Linear Algebra Appl,2010，433(1):19-27.

[9] M.L.Ye,Y.Z.Fan,D.Liang.The least eigenvalue of graphs with given connectivity[J].Linear Algebra Appl,2009，430(4):1375-1379.

[10] G.D.Yu,Y.Z.Fan,Y.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:213-236.

[11] Y.Z.Fan,F.F Zhang,Y.Wang.The least eigenvalue of the complements of tree[J].Linear Algebra Appl,2011，435(9):2150-2155.

[12] S.C.Li, S.J.Wang.The least eigenvalue of the signless Laplacian of the complements of trees[J].Linear Algebra Appl,2012，436(7):2398-2405.

[13] Y.Wang,Y.Z.Fan,X.X.Li,et al.The least eigenvalue of graphs whose complements are unicyclic[J].Discussiones Mathematicae Graph Theory,2013，35(2):1375-1379.

[14] G.D.Yu,Y.Z.Fan,Y.Wang.The least eigenvalue of graphs[J].Journal of mathematical research with application,2012，32(6):556-561.

[15] 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，17(2):81-88.

[16] W.haemers. Interlacing eigenvalues and graphs[J].Linear Algebra Appl,1995，226-228(95):593-616.

Study on the Minimum Eigenvalue of A Special Complement Graph

LIYu,XUETing-ting,SUNWei,WANGZhen-dong,HUANGXing

(AnqingNormalUniversity,Anqing246133,China)

The adjacency matrix is a matrix representation of adjacent relation between the vertex and the smallest eigenvalue is the minimum feature value. This paper discusses the special characteristics of complementary graph, and describes a special graph of this kind when the minimum eigenvalue reaches the minimum. The paper is of importance to future studies.

graph theory; adjacency matrix; complement graph; minimum eigenvalue

2017-04-12

國家自然科學基金資助項目(11604002，51607004)

李雨(1992-)，女，安慶師范大學計算機與信息學院在讀碩士研究生，研究方向：數據挖掘、文本分類。

黃星(1989-)，男，博士，安慶師范大學物理與電氣工程學院講師，研究方向：圖論與圖像處理。

O157.5

A

1674-3229(2017)02-0005-03