三類圖的拉普拉斯譜半徑的極限點(diǎn)

李靜花， 何常香

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

1 問題的提出

設(shè)為階 簡(jiǎn)單連通圖，其中，是圖的 點(diǎn)集合，是圖的邊集合。定義的 度對(duì)角矩陣，其 中 ，(表 示)點(diǎn)的度；若拉普拉斯矩陣為半正定奇異矩陣，設(shè)其特征值為。將圖的 最大拉普拉斯特征值稱為圖的 拉普拉斯譜半徑，記為。對(duì)于圖的拉普拉斯矩陣的特征多項(xiàng)式簡(jiǎn)記為。

1972年，Hoffman[1]研究了圖的特征根的極限點(diǎn)，并給出了圖的特征根的極限點(diǎn)的定義。類似地，本文給出圖的拉普拉斯譜半徑的極限點(diǎn)的定義。

定義1 對(duì)于實(shí)數(shù)，若存在一個(gè)圖序列，使得則稱實(shí)數(shù)是圖的拉普拉斯譜半徑的極限點(diǎn)。

文獻(xiàn)[2]研究了以下3類圖的拉普拉斯譜半徑的極限點(diǎn)：連通圖中 某1點(diǎn)與的1端通過1條邊相連（如圖1所示）；連通圖中某1點(diǎn)與2條內(nèi)點(diǎn)不交的的1端分別通過1條邊相連（如圖2所示）；的2個(gè)端點(diǎn)分別與2個(gè)頂點(diǎn)不相交的二部連通圖，中某1點(diǎn)通過1條邊相連（如圖3所示）。文獻(xiàn)[3]研究了圖的拉普拉斯特征值極限點(diǎn)集合的性質(zhì)，并確定了樹的代數(shù)連通度極限點(diǎn)前2大的值；文獻(xiàn)[4]研究了代數(shù)連通度極限點(diǎn)的性質(zhì)，并確定了樹的代數(shù)連通度前4大的值；文獻(xiàn)[5]確定了樹的代數(shù)連通度極限點(diǎn)的第5～14大的值。

圖1 Fig.1

圖 2G:(Pn,Pn)Fig.2G:(Pn,Pn)

圖3 (G,H):PnFig.3(G,H):Pn

本文主要研究如下3類圖的拉普拉斯譜半徑的極限點(diǎn)：連通圖中1點(diǎn)與多條內(nèi)點(diǎn)不相交的的1端點(diǎn)粘連（如圖4所示）；連通二部圖中 1點(diǎn)與1個(gè)中1點(diǎn)粘連（如圖5所示）；至少含1條邊的連通二部圖中1點(diǎn)與多個(gè)頂點(diǎn)不相交的中1點(diǎn)粘連（如圖6所示）。

圖 4Gv(s,n)Fig.4Gv(s,n)

圖 5G·CnFig.5G·Cn

圖6 (s,n)Fig.6(s,n)

本文直接引用的其他術(shù)語和記號(hào)參見文獻(xiàn)[6]。

2 主要引理

現(xiàn)介紹一些本文證明中需要用到的引理。

設(shè)是 簡(jiǎn)單連通圖，是圖添 加1條新邊后所得的圖，即。

引理1[7]圖和圖的拉普拉斯特征值滿足交錯(cuò)定理，即

推論1 若是圖的子圖，則有

進(jìn)一步地，若是圖的 真子圖，和的拉普拉斯譜半徑有引理2的關(guān)系。

引理2[8]若是連通二部圖的真子圖，則有

引理3[9]對(duì)于圖，有

若是連通圖，則等式成立當(dāng)且僅當(dāng)是二部正則圖或二部準(zhǔn)正則圖。

3 主要結(jié)果

圖 7Pv(3,2)Fig.7Pv(3,2)

參考文獻(xiàn)：

[1]HOFFMAN A J. On limit points of spectral radii of nonnegative symmetric integral matrices[M]//ALAVI Y, LICK D R, WHITE A T. Graph Theory and Applications. Berlin,Heidelberg： Springer, 1972, 303： 165-172.

[2]GUO J M. On limit points of Laplacian spectral radii of graphs[J]. Linear Algebra and its Applications, 2008,429(7)： 1705-1718.

[3]GUO J M. The limit points of Laplacian spectra of graphs[J]. Linear Algebra and its Applications, 2003, 362：121-128.

[4]KIRKAND S. A note on limit points for algebraic connectivity[J]. Linear Algebra and its Applications, 2003,373： 5-11.

[5]LIU Ying. The ordering of limit point of algebraic connectivity of trees[J]. Journal of Natural Science of Heilongjiang University, 2008, 25(1)： 103-106.

[6]BONDY J A, MURTY U S R. Graph theory with applications[M]. London： The Macmillan Press Ltd, 1976：6-258.

[7]GRONE R, MERRIS R, RSUNDE V S. The Laplacian spectrum of a graph[J]. SIAM Journal on Matrix Analysis and Applications, 1990, 11(2)： 218-238.

[8]GUO J M. On the Laplacian spectral radius of a tree[J].Linear Algebra and its Applications, 2003, 368： 379-385.

[9]ANDERSON W N JR, MORLEY T D. Eigenvalues of the Laplacian of a graph[J]. Linear and Multilinear Algebra,1985, 18(2)： 141-145.

[10]MERRIS R. Laplacian matrices of graphs： a survey[J].Linear Algebra and its Applications, 1994, 197/198：143-176.

[11]GUO J M. The Laplacian spectral radius of a graph under perturbation[J]. Computers & Mathematics with Applications, 2007, 54(5)： 709-720.

[12]GUO J M. A conjecture on the algebraic connectivity of connected graphs with fixed girth[J]. Discrete Mathematics, 2008, 308(23)： 5702-5711.

[13]GUO J M, LI J X, SHIU W C. On the Laplacian, singless Laplacian and normalized Laplacian characteristic polynomials of a graph[J]. Czechoslovak Mathematical Journal, 2013, 63(3)： 701-720.