關(guān)于圖的最小Q-特征值

吳寶豐，龐琳琳，沈富強(qiáng)

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

?

關(guān)于圖的最小Q-特征值

吳寶豐，龐琳琳，沈富強(qiáng)

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

研究了基于n階二部圖和s階完全圖構(gòu)造的一個(gè)圖類，得到了該圖類的無符號拉普拉斯最小特征值（即最小Q-特征值）的一個(gè)可達(dá)上界為s.基于此，對于任意給定的正整數(shù)s和正偶數(shù)n，構(gòu)造了最小Q-特征值為s的一類n + s階圖.另外，對于任意給定的

無符號拉普拉斯矩陣；最小Q-特征值；界；最小度

§1　引　言

本文考慮簡單無向圖.設(shè)圖G =（V，E），其中V = V（G）=｛1，2，···，n｝是G的頂點(diǎn)集，E = E（G）=｛ij?i，j∈V，且i～j｝是G的邊集，n稱為G的階數(shù). A（G）=（aij）表示G的鄰接矩陣，其中當(dāng)ij∈E（G）時(shí)，aij= 1；否則aij= 0. Q（G）= D（G）+A（G）表示G的無符號拉普拉斯矩陣，簡稱為G的Q-陣，其中D（G）= diag（d1，d2，···，dn）為G的度對角矩陣，di代表頂點(diǎn)i的度，δ（G）代表最小度，N（i）= NG（i）表示頂點(diǎn)i在G中的鄰點(diǎn)集.

近年來圖的Q-陣受到了國內(nèi)外眾多學(xué)者的關(guān)注，這主要?dú)w功于文獻(xiàn)［1-2］，因?yàn)樗鼈冿@示，對于圖的Q-陣，同譜不同構(gòu)的圖的數(shù)目要比鄰接矩陣和拉普拉斯矩陣少，這說明研究Q-陣可能更有意義.國際著名圖論專家Cvetkovi′c和Simi′c提出要建立Q-譜理論，并綜述了相關(guān)結(jié)論（見［3-5］），進(jìn)一步推動(dòng)了對Q-陣的研究.由于Q-陣的二次型為

所以Q（G）是半正定實(shí)對稱矩陣，它的特征值都是非負(fù)實(shí)數(shù)，記為qi（G）（i = 1，2，···，n），稱為圖G的Q-特征值，SpecQ（G）=｛q1（G），q2（G），···，qn（G）｝是一個(gè)多重集合，稱為圖G的Q-譜.不妨設(shè)特征值已從大到小排列為q1（G）≥q2（G）≥···≥qn（G）≥0，其中qmin（G）= qn（G）稱為G的最小Q-特征值，若x是Q（G）的相應(yīng)于特征值q的特征向量，則對于任意i = 1，2，···，n，有（q - di）xi=對于最小Q-特征值，若G是連通圖，則qmin（G）= 0當(dāng)且僅當(dāng)G是二部圖（見［6］），所以Desai和Rao（見［7］）等人提出以qmin（G）來衡量圖的非二部性，這說明研究圖的最小特征值qmin（G）是非常有意義的，相關(guān)文獻(xiàn)如［8-10］.

設(shè)a為實(shí)數(shù)，記「a?為不小于a的最小整數(shù)，即取a的上整.設(shè)G1，G2是兩個(gè)頂點(diǎn)不交的圖，G1VG2表示在G1∪G2的基礎(chǔ)上，連接G1和G2之間所有點(diǎn)對所得到的圖.設(shè)u，v分別是G1，G2中的點(diǎn)，G1u·vG2表示在G1∪G2的基礎(chǔ)上，合并u，v兩點(diǎn)所得到的圖.在不致混淆的情況下，G1u·vG2可以簡記為G1·G2.

§2研究了基于n階二部圖H和完全圖Ks構(gòu)造的一個(gè)圖類，得到了該圖類的最小Q-特征值的一個(gè)可達(dá)上界為s.基于此，對于任意給定的正整數(shù)s和正偶數(shù)n，構(gòu)造了最小Q-特征值為s的一類n+s階圖（定理1.1）.§3，對于任意給定的最小度δ和階數(shù)n，在滿足條件下，構(gòu)造了最小Q-特征值為δ- 1的一類n階圖（定理1.2）.

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

給定n階圖H，定義圖類

［11］研究了H為二部圖時(shí)圖類G（H，K1）的最小Q-特征值.本節(jié)研究H為二部圖時(shí)圖類G（H，Ks）（s≥1）的最小Q-特征值.

引理2.1 （見［12］）設(shè)λmin是n階實(shí)對稱矩陣A的最小特征值，則對于任意n維非零向量x，有，等式成立當(dāng)且僅當(dāng)x是A的相應(yīng)于λmin的特征向量.

引理2.2 （刪邊插值）（見［13］）設(shè)q1，q2，···，qn是圖G的Q-特征值，s1，s2，···，sn是G-e的Q-特征值，其中e是G的一條邊，則q1≥s1≥q2≥s2≥···≥qn≥sn≥0.

引理2.3 設(shè)n階二部圖H是圖G的一個(gè)點(diǎn)誘導(dǎo)子圖，H與G - H之間有t條邊，則qmin（G）≤進(jìn)一步，若等式成立，則對于任意i∈V（G - H），i在H兩部中的鄰點(diǎn)數(shù)相同.

證設(shè)H兩部的頂點(diǎn)集分別為V1，V2，其中|V1| = n1，|V2| = n2，n1+ n2= n.對于圖G，取x =（1，···，1，-1，···，-1，0，···，0）T，其中V1中的點(diǎn)對應(yīng)分量1，V2中的點(diǎn)對應(yīng)分量-1，其余點(diǎn)對應(yīng)分量0，由引理2.1知，

從而t1= t2.

綜上所述，結(jié)論得證.

定理2.1設(shè)二部圖H兩部的頂點(diǎn)數(shù)分別為n1，n2，G∈G（H，Ks），則qmin（G）≤s.進(jìn)一步，若等式成立，則（a）G = H V Ks；（b）n1= n2.

證設(shè)H與G - H之間有t條邊，則由引理2.3知，

進(jìn)一步，若qmin（G）= s，則上式所有不等式取到等號.第二個(gè)不等式取到等號時(shí)，顯然有G = H VKs.此時(shí)，考慮第一個(gè)不等式取到等號，根據(jù)引理2.3知，對于任意i∈V（Ks），i在H兩部中的鄰點(diǎn)數(shù)相同，從而n1= n2，證畢.

考慮H為正則二部圖，則G = H V Ks滿足定理2.1中等式成立的2個(gè)必要條件，在此基礎(chǔ)上，對于任意給定的正整數(shù)s和正偶數(shù)n，下面構(gòu)造最小Q-特征值為s的一類n + s階圖，記QG（x）= det（xI - Q（G））為G的無符號拉譜拉斯特征多項(xiàng)式，即G的Q-特征多項(xiàng)式.

引理2.4（見［14］）設(shè)G1為n1階r1-正則圖，G2為n2階r2-正則圖，則

其中f（x）= x2-［2（r1+ r2）+（n1+ n2）］x + 2（2r1r2+ r1n1+ r2n2）.

推論2.1設(shè)H為n階r-正則圖，則

定理2.2設(shè)H為n階r-正則二部圖，r≥1，n≥2r，則

（a）對于任意整數(shù)s∈｛1，2，···，2r｝，有qmin（H V Ks）= s；

證由推論2.1知，

其中qn（H）= 0，x1，x2為

的兩個(gè)根.設(shè)q為f（x）= 0的較小根，即

由于n≥2r≥2，所以

從而，qmin（H V Ks）= s等價(jià)于q≥s.經(jīng)計(jì)算知，q≥s又等價(jià)于

當(dāng)s = 2時(shí)，（1）式等價(jià)于（2r - 2）n≥0，顯然也成立，所以qmin（H V K2）= 2；

當(dāng)s∈｛3，···，2r｝時(shí)，（1）式的左邊大于等于0，而右邊小于0，從而（1）式成立，所以qmin（H V Ks）= s.

綜上所述，定理得證.

推論2.2設(shè)H為n階r-正則二部圖，r≥1，n≥2r，則有qmin（HVK1）= 1，qmin（HVK2）= 2.

推論2.3設(shè)H為簡單圖，若qmin（H VK1）＜1或者qmin（H VK2）＜2，則H不存在完美匹配.

證假設(shè)H存在完美匹配，則H的頂點(diǎn)數(shù)為偶數(shù)，不妨設(shè)為2t，則H包含1-正則生成子圖tK2，由引理2.2（刪邊插值）及推論2.2知，qmin（HVK1）≥qmin（tK2VK1）= 1，且qmin（HVK2）≥qmin（tK2V K2）= 2，矛盾，證畢.

引理2.5（見［11］）設(shè)G?是圖G增加一條邊e = ij后所得到的圖，x是G的相應(yīng)于qmin（G）的一個(gè)特征向量，若xi+xj= 0，則qmin（G?）= qmin（G），且x也是G?的相應(yīng)于qmin（G?）的一個(gè)特征向量.

定理1.1的證明對于任意給定的正整數(shù)s 和正偶數(shù)n， 顯然0，從而，即亦即令H為任意n階r-正則二部圖.若s≤2r，則由定理2.2（a）知，，則由r得，再根據(jù)定理2.2（b），得qmin（H V Ks）= s.

取x =（1，···，1，-1，···，-1，0，···，0）T，其中H的兩部分別對應(yīng)分量1，-1，Ks對應(yīng)分量0.

則

由引理2.1知，x =（1，···，1，-1，···，-1，0，···，0）T是相應(yīng)于qmin（H V Ks）的一個(gè)特征向量. 而H的二部之間任意點(diǎn)對（i，j），即i，j分屬于H的兩部，滿足xi+ xj= 0，根據(jù)引理2.5，在H的二部之間添加若干條邊后，H V Ks的最小Q-特征值保持不變，定理得證.

例2.1構(gòu)造最小Q-特征值分別為1和2的圖類.這里s = 1，2，對于任意正偶數(shù)n = 2t，有= 1，n階1-正則二部圖即為tK2，記

例2.2構(gòu)造最小Q-特征值分別為3和4的圖類.這里s = 3，4，當(dāng)n = 2時(shí)，有

2階1-正則二部圖即為K2；當(dāng)正偶數(shù)n≥4時(shí)，有

2-正則二部圖即為若干個(gè)偶圈的并，記

則任意G∈｛K2V K3｝∪π3，有qmin（G）= 3；任意G∈｛K2V K4｝∪π4，有qmin（G）= 4.

§3　最小Q-特征值為δ- 1的一類圖

眾所周知，當(dāng)圖G（階數(shù)＞1）連通時(shí)，qmin（G）＜δ（G）（見［15］），下面構(gòu)造最小Q-特征值為δ（G）- 1的一類n階圖.

引理3.1設(shè)n階圖G的最小度為δ，度為δ的頂點(diǎn)至少有2個(gè)，且它們相鄰，則qmin（G）≤δ-1.

引理3.2設(shè)G =（V，E），Vk?V，|Vk| = k，G［Vk］是一個(gè)團(tuán)，且Vk中任一點(diǎn)在V Vk中有相同的鄰點(diǎn)集，設(shè)Vk中點(diǎn)的度為d，則d - 1至少是Q（G）的k - 1重特征值.

證設(shè)Vk=｛1，2，···，k｝，x =（x1，···，xk，xk+1，···，xn）T，其中xi對應(yīng)頂點(diǎn)i（i = 1，···，n），且x1+···+ xk= 0，xk+1=···= xn= 0，則對于任意i∈Vk，有

對于任意i∈V Vk，或者Vk?N（i），或者Vk∩N（i）=?，從而

故x是Q（G）的相應(yīng)于d-1的特征向量，且d-1的特征子空間的維數(shù)至少為k -1，所以d-1至少是Q（G）的k - 1重特征值.

引理3.3設(shè)G = Kn1·Kn2，n1≥2，n2≥2，則

其中f（x）= x2-（2n1+ 2n2- 5）x + 4n1n2- 6n1- 6n2+ 8.

證設(shè)Kn1和Kn2的公共點(diǎn)為u，V1= V（Kn1）｛u｝，V2= V（Kn2）｛u｝，則V1，V2都是團(tuán)，由引理3.2知，G = Kn1·Kn2的Q-譜中包含n1-2個(gè)特征值n1-2以及n2-2個(gè)特征值n2-2.剩下的3個(gè)特征值可按如下方法求得.設(shè)x是Q（G）的特征向量，點(diǎn)u對應(yīng)分量x0，V1中的點(diǎn)都對應(yīng)分量x1，V2中的點(diǎn)都對應(yīng)分量x2，則有

即

相應(yīng)的特征多項(xiàng)式為

它的3個(gè)實(shí)數(shù)根也是Q（G）的特征值，且與n1-2個(gè)特征值n1-2以及n2-2個(gè)特征值n2-2并不重復(fù)，因?yàn)橐?.2的證明表明那些特征值的特征向量在V1中對應(yīng)的分量是不能全相等的，結(jié)論得證.

推論3.1設(shè)G = Kn1·Kn2，2≤n1≤n2，則Q（G）的最小特征值為n1- 2.

證根據(jù)引理3.3，

其中x1，x2是f（x）= x2-（2n1+ 2n2- 5）x + 4n1n2- 6n1- 6n2+ 8的兩個(gè)根.

顯然n1+ n2- 3＞n2- 2≥n1- 2，所以Q（G）的最小特征值是f（x）的最小根和n1- 2兩者之一.因?yàn)閒（x）的對稱軸為

且

所以n1- 2小于等于f（x）的最小根，從而Q（G）的最小特征值為n1- 2，證畢.

定理1.2的證明任意G∈σδ，n，顯然δ（G）=δ，下證qmin（G）=δ- 1.

綜上所述，qmin（G）=δ- 1.

［1］Van Dam E R，Haemers W H. Which graphs are determined by their spectrum？［J］. Linear Algebra Appl，2003，373: 241-272.

［2］Haemers W，Spence E. Enumeration of cospectral graphs［J］. Eur J Combin，2004，25: 199-211.

［3］Cvetkovi′c D，Simi′c S K. Towards a spectral theory of graphs based on signless Laplacian，I［J］. Publ Inst Math，2009，85（99）: 19-33.

［4］Cvetkovi′c D，Simi′c S K. Towards a spectral theory of graphs based on signless Laplacian，II［J］. Linear Algebra Appl，2010，432（9）: 2257-2272.

［5］Cvetkovi′c D，Simi′c S K. Towards a spectral theory of graphs based on signless Laplacian，III［J］. Appl Anal Discrete Math，2010，4（1）: 156-166.

［6］Cvetkovi′c D，Rowlinson P，Simi′c S K. Signless Laplacians of finite graphs［J］. Linear Algebra Appl，2007，423: 155-171.

［7］Desai M，Rao V. A characterization of the smallest eigenvalue of a graph［J］. J Graph Theory，1994，18: 181-194.

［8］Cardoso D M，Cvetkovi′c D，Rowlinson P，et al. A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph［J］. Linear Algebra Appl，2008，429（11-12）: 2770-2780.

［9］Lima L S，Silvaoliveira C，Abreu N M M，et al. The Smallest eigenvalue of the Signless Laplacian［J］. Linear Algebra Appl，2011，435（10）: 2570-2584

［10］Fan Yizheng，Wang Yi，Guo Huan. The least eigenvalues of the signless Laplacian of nonbipartite graphs with pendant vertices［J］. Discrete Math，2013，313（7）: 903-909.

［11］沈富強(qiáng)，吳寶豐.最小Q-特征值為給定整數(shù)的一類圖［J］.上海理工大學(xué)學(xué)報(bào)，2014，36（5）: 425-428.

［12］Horn R A，Johnson C R. Matrix Analysis［M］. Cambridge: Cambridge University Press，1985.

［13］Cvetkovi′c D，Rowlinson P，Simi′c S K. Eigenvalue bounds for the signless Laplacian［J］. Publ Inst Math，2007，81（95）: 11-27.

［14］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.

［15］Das K C. On conjectures involving second largest signless Laplacian eigenvalue of graphs［J］. Linear Algebra Appl，2010，432: 3018-3029.

MR Subject Classification: 05C50

On the least signless Laplacian eigenvalue of graphs

WU Bao-feng，PANG Lin-lin，SHEN Fu-qiang
（College of Science，University of Shanghai for Science and Technology，Shanghai 200093，China）

A class of graphs constructed by H and Kswas studied，where H is a bipartite graph of order n and Ksis the complete graph of order s. It was shown that a sharp upper bound of the least signless Laplacian eigenvalue（the least Q-eigenvalue）is s. Based on this，for any given positive integer s and positive even number n，a class of graphs of order n + s was constructed which have eigenvalue s as their least Q-eigenvalue. Also，for any given smallest degree δ and order n such that 2≤δ≤， a class of graphs of order n was constructed which have eigenvalue δ- 1 as their least Q-eigenvalue.

signless Laplacian matrix；least Q-eigenvalue；bound；smallest degree

O157.5

A

1000-4424（2016）01-0083-07

2015-05-24

2015-12-11

國家自然科學(xué)基金（11301340；11201303）；上海自然科學(xué)基金（12ZR1420300）；滬江基金（B14005）