圖的拉普拉斯譜半徑對應的特征向量性質(zhì)及其應用

汪秋分，宋海洲

（華僑大學 數(shù)學科學學院，福建 泉州362021）

設G是一個簡單的連通圖［1］，G＝（V，E）.其頂點集V＝｛v1，v2，…，vn｝，邊集E＝｛e1，e2，…，em｝.記頂點vi的度為di，i＝1，2，…，n.記D（G）＝diag｛d1，d2，…，dn｝和A（G）分別為G的度對角矩陣和鄰接矩陣［2］，則L（G）＝D（G）－A（G）為G的拉普拉斯矩陣［3］.顯然，L（G）是半正定、對稱和奇異的.稱L（G）的特征值為G的拉普拉斯特征值，記為μ（G）＝μ1（G）≥μ2（G）≥…≥μn（G）＝0.特別的，稱μ（G）為G的拉普拉斯譜半徑［4］.樹是含n個頂點，n－1條邊的簡單連通圖.圖G中所有的度為1的頂點稱為圖G的懸掛點［5］.記NG（v）表示圖G中與v相鄰接的頂點集，dv表示圖G中頂點v的度.有關圖的拉普拉斯譜半徑的結果有很多，如郭繼明［6］的加邊或嫁接邊對圖的拉普拉斯譜半徑的影響，袁西英等［7］的樹的運算及其Laplace譜，郭繼明［8］的樹的拉普拉斯譜半徑，譚尚旺［9］的關于樹的拉普拉斯譜半徑，張曉東［10］的給定度序列的樹的拉普拉斯譜半徑，等等.本文給出了圖的拉普拉斯譜半徑對應的特征向量的性質(zhì)及應用，并得到了一些有關圖的移接變形對拉普拉斯譜半徑影響的結果.

1 相關定義與性質(zhì)

1.1 圖的拉普拉斯譜半徑對應的特征向量的定義

介紹其定義之前，先證明一個定理.

定理1設G＝（V，E）是一個簡單的連通圖，且｜V｜＝n.記L（G）為圖G的拉普拉斯矩陣，有時也簡記為L，μ（G）為圖G的拉普拉斯譜半徑.則對于向量x∈Rn×1，有

1）μ（G）＝為L（G）的n個特征值；

2）μ（G）＝

3）若‖x‖＝1，且x′L（G）x＝μ（G），則L（G）x＝μ（G）x.

證明 1）由拉普拉斯譜半徑的定義容易證明.

2）由于L（G）是一個實對稱矩陣，因此，存在一個正交矩陣P，使得P－1LP＝diag（μ1，μ2，…，μn），其中，μ1，μ2，…，μn為L（G）的n個實特征值.

令diag（μ1，μ2，…，μn）＝D，P＝（P1，P2，…，Pn），x＝Py，則有

又由于P是正交矩陣，并且有x＝Py.因此，當‖x‖＝1時，有‖y‖＝1.不失一般性，可假設μ1≤μ2≤…≤μn.因而有

令y＊＝en＝（0，0，…，0，1）′n×1，記x＊＝Py＊＝Pn，則上面不等式等號成立.因此有

3）設μ1，μ2，…，μn為L（G）的n個特征值，P，D，y的含義同2）.不失一般性，可設μ1≤μ2≤…≤μn.則由1）可知μ（G）＝μn.又由于x′L（G）x＝μ（G），因此x′L（G）x＝y(tǒng)′Dy＝μ（G）＝μn.即有y′Dy＝μn.

易知L（G）是一個實對稱半正定矩陣，且μ1＝0，μn＞0.不妨假設實數(shù)s（1≤s≤n）是滿足μs＜μs＋1且μs＋1＝μn的最大自然數(shù).所以y＝（01×s，Z）1×n，其中，實向量Z∈R1×（n－s）且‖Z‖＝1.記Z＝（ys＋1，ys＋2，…，yn），則有可知x是L（G）的對應于的特征向量，因此有L（G）x＝μ（G）x.

下面給出圖的拉普拉斯譜半徑對應的特征向量的定義.

定義1設G＝（V，E）是一個簡單的連通圖.若向量x∈Rn×1滿足‖x‖＝1，且x′L（G）x＝μ（G），則稱x為圖G的一個規(guī)范拉普拉斯譜向量.

1.2 圖的拉普拉斯譜半徑對應的特征向量的性質(zhì)

下面給出有關圖的拉普拉斯譜半徑對應的特征向量的一些性質(zhì).

定理2設T是一棵樹，其頂點集V＝｛v1，v2，…，vn｝.記L（T）為T的拉普拉斯矩陣，μ（T）為T的拉普拉斯譜半徑.若x為T的一個規(guī)范拉普拉斯譜向量，且x＝（x1，x2，…，xn）′.則有：1）x為實向量；2）｜x｜＞0，其中，｜x｜＝（｜x1｜，｜x2｜，…，｜xn｜）′.

證明 1）由題意可知：L（T）是實對稱矩陣.又μ（T）也為實數(shù)，因此，x為實向量.

2）反證法.假設｜x｜＞0不成立，必然存在一個頂點集H＝｛vj1，vj2，…，vjt｝，使xjl＝0（l＝1，2，…，t），其中，1≤t≤n，1≤j≤n，xj為頂點vj對應于一個規(guī)范拉普拉斯譜向量的分量.

又由于x為T的一個規(guī)范拉普拉斯譜向量，因而有‖x‖＝1.所以x≠0，且存在頂點v∈V（T）使得xv＝0，及頂點u∈NT（v）使得xu≠0.

設T是以頂點v為根節(jié)點的根樹，記NT（v）＝｛w1，w2，…，ws｝.另記Ti為由wi及wi的所有子孫組成的子樹，i＝1，2，…，s.令yv＝xv＝0，ywi＝｜xwi｜，當xwi≥0時，有yj＝xj（vj∈Ti），當xwi＜0時，有yj＝－xj（vj∈Ti），i＝1，2，…，s.

因此，有ywi≥0，i＝1，2，…，s，‖y‖＝1且y′L（T）y＝x′L（T）x＝μ（T）.由定義1可知，y是T的一個規(guī)范拉普拉斯譜向量.根據(jù)定理1可得L（T）y＝μ（T）y.又已知L（T）＝D（T）－A（T），則（D（T）－A（T））y＝μ（T）y.故（（D（T）－μ（T）I）y）v＝（A（T）y）v.因此可得

然而ywi≥0，且存在i0＝∈｛1，2，…，s｝，使得wi0＝u滿足yu＞0.因而，從而導致矛盾，原命題成立.

定理3設T是一棵樹，v是T的一個頂點，v1，v2，…，vs是與v相鄰的懸掛點.若x＝（x1，x2，…，xn）′為T的一個規(guī)范拉普拉斯譜向量，這里xi對應于頂點vi，1≤i≤n，則xvj＝xvi，1≤i＜j≤s.

證明 由于x＝（x1，x2，…，xn）′為T的一個規(guī)范拉普拉斯譜向量，由定理1及定義1可得

又已知L（T）＝D（T）－A（T），則有（D（T）－A（T））x＝μ（T）x，所以可得（（D（T）－μ（T）I）x）vi＝（A（T）x）vi＝xv，i＝1，2，…，s.從而有（1－μ（T））xv1＝xv，（1－μ（T））xv2＝xv，…，（1－μ（T））xvs＝xv.因此xvj＝xvi（1≤i＜j≤s）.

定理4設T＝（V，E）是一棵樹，其頂點集V（T）＝｛v1，v2，…，vn｝，邊集記為E（T）.若x＝（x1，x2，…，xn）′為T的一個規(guī)范拉普拉斯譜向量，xi對應于頂點vi，1≤i≤n.則有：1）對于任意邊uv∈E（T），有

證明 1）由于x為T的一個規(guī)范拉普拉斯譜向量，由定義1可得

對任意uv∈E（T），由定理2可得｜xu｜＞0且｜xv｜＞0，所以有xuxv≠0.

設存在邊uv∈E（T）使得xuxv＞0.設T是以r為根節(jié)點的根樹，可設頂點u是頂點v的父節(jié)點（圖1）.設T1＝（V1，E1）是由v及v的所有子孫組成的k層子樹（圖2）.不失一般性，假設xu＞0，故xv＞0.

取y＝（y1，y2，…，yn）′，令yi＝xi（i?V1），yw1＝－｜xw1｜（w1是T1的第1層上的頂點，即w1＝v），yw2＝（－1）2｜xw2｜（任意w2是T1的第2層上的頂點），…，ywk＝（－1）k｜xwk｜（任意wk是T1的第k層上的頂點）.則有‖y‖＝‖x‖＝1，且有

圖1 頂點u是頂點 v的父節(jié)點 Fig.1 Vertex uis the father vertex of vertex v

圖2 v及v的所有子孫 組成的k層子樹Fig.2 Subtree with klevels obtained fromv and v′s descendants

因此，存在一個單位向量y＝（y1，y2，…，yn）′，使μ（T）＜y′L（T）y.這與定理1矛盾，故有xuxv＜0.

2）由于x為T的一個規(guī)范拉普拉斯譜向量，因而有（D（T）－A（T））x＝μ（T）x.因此（dvi－所 以 有從 而，所以

2 圖的拉普拉斯譜半徑對應的特征向量的應用

2.1 加邊對圖的拉普拉斯譜半徑的影響

定理5設u，v是樹T的兩個頂點.記頂點u，v之間的距離為d（u，v）＝k，其中，k為奇數(shù)且k≥3.若G是由T添加新邊設uv后所得到的圖，則有μ（G）＞μ（T）.

證明 設x＝（x1，x2，…，xn）′為T的一個規(guī)范拉普拉斯譜向量，xi對應于頂點vi，1≤i≤n.由于k為奇數(shù)且k≥3，由前面定理4可得：xuxv＜0.記T與G的邊集分別為E（T）和E（G），因此有

即μ（G）＞μ（T）.

2.2 嫁接對圖的拉普拉斯譜半徑的影響

定理6設u，v是樹T的兩個頂點，T＝（V（T），E（T）），且有NT（v）／（NT（u）∪｛u｝）＝｛v1，v2，…，vs｝，1≤s≤dv，設x＝（x1，x2，…，xn）′為T的一個規(guī)范拉普拉斯譜向量，xi對應于頂點vi，1≤i≤n，T＊是由T刪除邊vvi，添加邊uvi后所得到的樹（1≤i≤s）（圖3）.若｜xu｜≥｜xv｜，則μ（T）＜μ（T＊）.

證明 對于樹T，設T＝（V，E）形成一根樹，且頂點v是v1，v2，…，vs的父節(jié)點.令T1是由頂點v，v1，v2，…，vs及v1，v2，…，vs的所有子孫組成的子樹，T1＝（V1，E1）.類似的，對于樹T＊，設T＊＝（V＊，E＊）形成一根樹，u為其根節(jié)點，并且頂點u是v1，v2，…，vs的父節(jié)點.令T＊1是由頂點u，v1，v2，…，vs及v1，v2，…，vs的所有子孫組成的子樹，且T＊1的層次（高度加1）為k.記E′1＝E1／｛vv1，vv2，…，vvs｝.

令yi＝xi（vi∈V／V（T1）），yv＝xv，yw1＝－sgn（xu）｜xw1｜（任意w1是T＊1的第2層上的頂點），yw2＝（－1）2sgn（xu）｜xw2｜（任意w2是T＊1的第3層上的頂點），…，ywk－1＝（－1）k－1sgn（xu）｜xwk－1｜（任意wk－1是T＊1的第k層上的頂點）.則可得‖y‖＝1，且

圖3 樹T和樹T＊Fig.3 Tree Tand T＊

即有y′L（T＊）y≥x′L（T）x.因此

故有μ（T）≤μ（T＊）.

若μ（T）＝μ（T＊），則式（1）中等號成立，故有μ（T）＝y(tǒng)′L（T＊）y＝μ（T＊）.因而，由定理1可以得L（T＊）y＝μ（T＊）y.又L（T＊）＝D（T＊）－A（T＊），所以

式（2）中：dT＊（v）為頂點v在樹T＊中的度.

又L（T）x＝μ（T）x，類似的有

由式（2）～（3）可得

不失一般性，設xv＞0.

若xu＞0，由定理4可得因而有μ（T）＞μ（T＊），這與假設矛盾.

若xu＜0，由定理4可得有μ（T）＞μ（T＊），這也與假設矛盾.

綜上所述，若｜xu｜≥｜xv｜，則μ（T）＜μ（T＊）.

推論1設T＊是如定理6所定義的樹，若y＝（y1，y2，…，yn）′為T＊的一個規(guī)范拉普拉斯譜向量，yi對應于頂點vi，1≤i≤n，則｜yu｜＞｜yv｜.

證明 反證法.若｜yu｜≤｜yv｜，由定理6可得μ（T）＞μ（T＊）.這與定理6結論矛盾，顧原命題成立.

推論2設G＝（V，E）為含n個頂點的樹，r，s，t是G的三個不同的頂點，且rs∈E（G），rt?E（G）.設G＊是由G刪除邊rs添加邊rt后所得到的樹.設x＝（x1，x2，…，xn）′為G的一個規(guī)范拉普拉斯譜向量，xi對應于頂點vi，1≤i≤n；x＊＝（x＊1，x＊2，…，x＊n）′為G＊的一個規(guī)范拉普拉斯譜向量，x＊i對應于頂點v＊i，1≤i≤n.若｜xt｜≥｜xs｜，則｜x＊t｜＞｜x＊s｜.

證明 顯然，由題意可知，G是由G＊刪除邊rt添加邊rs后所得到的樹.假設｜x＊t｜≤｜x＊s｜，由定理6可得μ（G）＞μ（G＊）.又｜xt｜≥｜xs｜，由定理6得μ（G）＜μ（G＊）.這樣導致矛盾，因此原命題成立.

［1］汪秋分，宋海洲.圖譜理論中一些定理的新證明［J］.華僑大學學報：自然科學版，2012，33（4）：477－480.

［2］劉亞國.圖論中鄰接矩陣的應用［J］.忻州師范學院學報，2008，24（4）：18－19.

［3］譚尚旺，張德龍.一定條件下圖的拉普拉斯矩陣的譜半徑［J］.廣西科學，2008，15（4）：352－356.

［4］LI Jian－xi，SHIU Wai－chee，CHAN Wai－h(huán)ong.The Laplacian spectral radius of some graphs［J］.Linear Algebra Appl，2009，431（1）：99－103.

［5］WU Bao－feng，XIAO En－li，HONG Yuan.The spectral radius of trees onkpendant vertices［J］.Linear Algebra Appl，2005，395（15）：343－349.

［6］GUO Ji－ming.The effect on the Laplacian spectral radius of a graph by adding or grafting edges［J］.Linear Algebra Appl，2006，413（1）：59－71.

［7］袁西英，吳寶豐，肖恩利.樹的運算及其Laplace譜［J］.華東師范大學學報：自然科學版，2004，50（2）：13－18.

［8］GUO Ji－ming.On the Laplacian spectral radius of a tree［J］.Linear Algebra Appl，2003，368（15）：379－385.

［9］TAN Shang－wang.On the Laplacian spectral radius of trees［J］.Chinese Quarterly Journal of Mathematics，2010，25（4）：615－625.

［10］ZHANG Xiao－dong.The Laplacian spectral radii of trees with degree sequences［J］.Discrete Mathematics，2008，308（15）：3143－3150.