沈富強， 吳寶豐

（上海理工大學(xué)理學(xué)院，上海 200093）

最小Q-特征值為給定整數(shù)的一類圖

沈富強， 吳寶豐

（上海理工大學(xué)理學(xué)院，上海 200093）

研究了基于二部圖H構(gòu)造的一類圖的最小無符號拉普拉斯特征值，即最小Q-特征值，得到了它的最小Q-特征值的可達上界為1.給出了最小Q-特征值為1的2個必要條件，并構(gòu)造了最小Q-特征值為1的一類圖.另外，給出了利用H∨K1的最小Q-特征值來判斷簡單圖H沒有完美匹配的方法，以及圖G增加邊后最小Q-特征值保持不變的1個充分條件.最后，構(gòu)造了最小Q-特征值為任意給定的正整數(shù)t的一類圖.

無符號拉普拉斯矩陣；最小Q-特征值；界；完美匹配

1 基本概念

設(shè)G=（V，E）是簡單圖（不含環(huán)和重邊），其中，V=V（G）=｛v1，v2，…，vn｝為頂點集，n為頂點數(shù)，也稱為G的階數(shù)，E=E（G）為邊集.A（G）= （aij）為G的鄰接矩陣，當(dāng)vi和vj相鄰時，aij=1；不相鄰時，aij=0.dG（vi）=｜NG（vi）｜為頂點vi的度，簡記為di（i=1，2，…，n），D（G）=diag（d1，d2，…，dn）為度對角矩陣.在不致混淆的情況下，頂點集也記為｛1，2，…，n｝.

本文用qmin（G）表示圖G的最小Q-特征值，相應(yīng)的特征向量稱為最小特征向量.qmin（G）≤δ（G），且當(dāng)G（階數(shù)n＞1）連通時，qmin（G）＜δ（G）［2］，其中，δ（G）為G的最小度.眾所周知，圖G是二部圖當(dāng)且僅當(dāng)qmin（G）=0［3］，可以利用最小Q-特征值來判別圖的二部性.

2 G（H）的最小Q－特征值

引理1［4］設(shè)A，B均為n階實對稱矩陣，則對于任意i=1，2，…，n，有

推論1 設(shè)A，B均為n階實對稱矩陣，則λn（A+B）≤λn-1（A）+λ2（B）.

定理1 設(shè)H為二部圖，則任意G∈G（H），有qmin（G）≤1.

證明 設(shè)H外的那一點與H之間有k條邊相連.當(dāng)k=0時，qmin（G）=0＜1.當(dāng)k=1時，qmin（G）≤δ（G）≤1，結(jié)論也成立.現(xiàn)證明k≥2的情形，設(shè)｜V（G）｜=n，則

式中，J為全1矩陣；I為單位矩陣，則Spec（B）= （k+1，1k-1，0n-k），λn-1（A）=qmin（H）=0，λ2（B）=1.由推論1可知，qmin（G）≤qmin（H）+ 1=1.

引理4 設(shè)V1是圖G的一個獨立集，V1中任一點的鄰點集均為V2，則G的Q-譜中至少包含｜V1｜-1個特征值｜V2｜.

證明 記V3=V（G）＼（V1∪V2），設(shè)x是｜V（G）｜維向量，其中，V2∪V3對應(yīng)分量0，V1對應(yīng)分量x1，x2，…，x｜V1｜，滿足x1+x2+…+ x｜V1｜=0，則

對于V1中的點i，

引理5 設(shè)G為完全三部圖K1，r，s，若r≠s，則qmin（G）＜1.

證明 K1，r，s=Kr，s∨K1∈G（Kr，s），根據(jù)定理1，qmin（G）≤1，現(xiàn)只需證1不是Q（G）的特征值.設(shè)V1，V2是Kr，s的二部，其中，｜V1｜=r，｜V2｜=s，r+s=n-1，由引理4可知，G的Q-譜中包含r-1個特征值s+1，以及s-1個特征值r+1.其余3個特征值可以通過后面定義的矩陣B來求得. 設(shè)x是Q（G）的特征向量，V1對應(yīng)分量x1，V2對應(yīng)分量x2，余下那一點對應(yīng)分量x0，則有

則φ（B，1）=det（I-B）=（r-s）2，從而當(dāng)r≠s時，1不是Q（G）的特征值，所以，qmin（H）＜1.

文獻［6］提出了一個問題：是否存在Kp 1，p 2，…，ps （s≥3）是Q-整圖，引理5表明，當(dāng)s=3時，若p1=1，p2≠p3時，它的最小Q-特征值小于1大于0，故此時Kp 1，p2，p3不可能為Q-整圖.

定理2 設(shè)二部圖H的兩部的頂點數(shù)分別為r 和s，若r≠s，則任意G∈G（H），有qmin（G）＜1.

證明 顯然G為K1，r，s的生成子圖，由引理3（刪邊插值）和引理5得，qmin（G）＜1.

引理6 設(shè)G為K1，r，s中刪除K1與Kr，s之間的1條邊后所得到的圖，則qmin（G）＜1.

證明 G∈G（Kr，s），由定理1可知，qmin（G）≤1，現(xiàn)只需要證qmin（G）≠1即可.設(shè)V1，V2是Kr，s的二部，若qmin（G）=1，由定理2可知，兩部的頂點數(shù)相等，不妨均記為s，由引理4可知，G的Q-譜中包含2s-3個特征值s+1，其余4個特征值可通過后面定義的矩陣B來求得.設(shè)v∈V1是唯一不與K1相鄰的點，x是Q（G）的特征向量，K1對應(yīng)分量x0，V1＼｛v｝對應(yīng)分量x1，V2對應(yīng)分量x2，v對應(yīng)分量x3，則有

則φ（B，1）=det（I-B）=-2s（s-1）.當(dāng)s≥2時，1不是B的特征值.當(dāng)s=1時，1為B的特征值，但此時G=P3，最小特征值為0，所以，qmin（G）＜1.

定理3 設(shè)H為二部圖，G∈G（H），若G≠H∨K1，則qmin（G）＜1.

證明 根據(jù)引理3（刪邊插值）和引理6.

結(jié)合定理1～3，得到圖類G（H）中最小Q-特征值為1的圖的2個必要條件，即定理4.

定理4 設(shè)二部圖H的兩部的頂點數(shù)分別為r 和s，G∈G（H），若qmin（G）=1，則

a.r=s；

b.G=H∨K1.

3 最小Q－特征值為1的一類圖

引理7［7］設(shè)G1為n1階r1-正則圖，G2為n2階r2-正則圖，則

引理8 設(shè)G=sK2∨K1，s≥1，則qmin（G）= 1，且x=（1，…，1，-1，…，-1，0）T是G的1個最小特征向量，其中，sK2的二部分別對應(yīng)分量1，-1，K1對應(yīng)分量0.

證明 sK2是1-正則二部圖，根據(jù)定理5，qmin（G）=1.另一方面，

由引理2可知，x=（1，…，1，-1，…，-1，0）T是Q（G）的相應(yīng)于1的特征向量，即最小特征向量.

定理6 設(shè)H為簡單圖，若qmin（H∨K1）＜1，則H不存在完美匹配.

證明 假設(shè)H存在完美匹配，設(shè)H的頂點數(shù)為2s，則H包含1-正則生成子圖sK2，由引理3（刪邊插值）及引理8得，qmin（H∨K1）≥qmin（sK2∨K1）=1，矛盾.

定理7 設(shè)G是圖H增加1條邊e=uv后所得到的圖，x是Q（H）的最小特征向量，若xu+xv=0，則qmin（H）=qmin（G），且x也是Q（G）的最小特征向量.

根據(jù)引理8和定理7，若G=sK2∨K1，在sK2的二部之間隨意添加邊，G的最小特征值保持不變.于是，得到一類圖，它的最小特征值均為1.記π=｛H∨K1｜H是在sK2的二部之間添加若干條邊后所得到的圖，s為任意正整數(shù)｝，則任意G∈π，有qmin（G）=1，此時，H總包含1-正則生成子圖sK2，故H存在完美匹配.于是，有定理8.

定理8 設(shè)H為二部圖，存在完美匹配，G= H∨K1，則qmin（G）=1，且x=（1，…，1，-1，…，-1，0）T是G的最小特征向量，其中，H的二部分別對應(yīng)分量1，-1，K1對應(yīng)分量0.

在定理8中，H存在完美匹配并不是qmin（H∨K1）=1成立的必要條件，圖1中的H∨K1的Q-譜為（8，42，22，12），顯然，qmin（H∨K1）=1，但H沒有完美匹配.

圖1 H∨K1Fig.1 H∨K1

4 最小Q-特征值為t的一類圖

引理9的證明類似引理8，再根據(jù)定理7，對圖加邊后最小Q-特征值不變的條件，得到定理10，定理10給出了最小Q-特征值為任意給定的正整數(shù)t的一類圖.

［1］ Cvetkovic＇D，Doob M，Sachs H.Spectra of graphs：theory and applications［M］.New York：Academic Press，1980.

［2］ Das K C.On conjectures involving second largest signless Laplacian eigenvalue of graphs［J］.Linear Algebra Appl，2010，432（11）：3018-3029.

［3］ Cvetkovic＇D，Rowlinson P，Simic＇S K.Signless Laplacians of finite graphs［J］.Linear Algebra Appl，2007，423（1）：155-171.

［4］ Horn R A，Johnson C R.Matrix analysis［M］.Cambridge：Cambridge University Press，1985.

［5］ Cvetkovic＇D，Rowlinson P，Simic＇S K.Eigenvalue bounds for the signless Laplacian［J］.Publ Inst Math，2007，81 （95）：11-27.

［6］ Zhao G P，Wang L，Li K.Q-integral complete r-partite graphs［J］.Linear Algebra Appl，2013，438（13）：1067 -1077.

［7］ de Freitas M A A，de Abreu N M M，Del-Vecchio R R，et al.Infinite families of Q-integral graphs［J］.Linear Algebra Appl，2010，432（9）：2352-2360.

（編輯：石 瑛）

A Class of Graphs with a Given Integer as Least Q-eigenvalue

SHENFu-qiang， WUBao-feng
（College of Science，University of Shanghai for Science and Technology，Shanghai 200093，China）

When H is a bipartite graph，the least signless Laplacian eigenvalue（the least Q- eigenvalue）of a class of graphs constructed by H was studied.It was shown that the sharp upper bound of the least Q-eigenvalue of the class of graphs is 1.Moreover，two necessary conditions were given for the graphs whose least Q- eigenvalue is equal to 1，and a class of graphs was constructed which have eigenvalue 1 as their least Q- eigenvalue.Also，a method was presented for checking a graph H without a perfect matching by using the least Q eigenvalue of H∨K1，and a sufficient condition was given when adding edges without changing the least Q- eigenvalue.At last，a class of graphs were constructed which have least Q-eigenvalue t，where t is a given positive integer.

signless Laplacian matrix；least Q- eigenvalue；bound；perfect matching

O 157.5文獻標示碼：A

1007-6735（2014）05-0425-04

10.13255／j.cnki.jusst.2014.05.003

2013-08-16

國家自然科學(xué)基金資助項目（11301340，11201303，11101284）；上海市自然科學(xué)基金資助項目（12ZR1420300）

沈富強（1988-），男，碩士研究生.研究方向：代數(shù)圖論.E-mail：shenfuqiang19881230＠126.com

吳寶豐（1978-），男，講師.研究方向：代數(shù)圖論.E-mail：baufern＠usst.edu.cn