含割邊的連通圖最小距離無符號拉普拉斯譜半徑

查淑萍，李路遙，高　芳

（池州學院 數(shù)學與計算機學院，安徽 池州 247000）

含割邊的連通圖最小距離無符號拉普拉斯譜半徑

查淑萍，李路遙，高芳

（池州學院 數(shù)學與計算機學院，安徽 池州 247000）

在所有含割邊的n階連通圖中，利用特征值與特征向量的關系，刻畫了具有最小距離無符號拉普拉斯譜半徑的圖的結構，在此基礎上，給出了含割邊的n階連通圖的距離無符號拉普拉斯譜半徑的一個下界。

圖；割邊；距離無符號拉普拉斯矩陣；譜半徑

1　引言

本文中，我們只考慮簡單的連通圖G=（V（G），E（G），這里V（G）表示圖G的頂點集，E（G）表示圖G的邊集，其中||V（G）稱為圖G的階數(shù)。圖G的距離矩陣，記作D（G），定義為D（G）=（duv）u，v∈V（G），其中duv表示頂點u和v之間的距離（即G中連接u和v的最短路的長度）。其廣泛應用涉及很多領域，如通訊網(wǎng)絡的設計［1］，圖的嵌入理論［2-4］以及分子穩(wěn)定性［5-6］等。頂點v的距離度，記作Tr（v），定義為v與G中所有頂點的距離之和，即Tr（v）=∑u∈V（G）duv，記G中頂點的最大距離度為Trmax（G）。

2013年，M.Aouchiche和P.Hanse［7］在距離矩陣的基礎上，定義了連通圖G的距離無符號拉普拉斯矩陣為DQ（G）=Diag（Tr）+D（G），這里Diag（Tr）表示以G的各頂點的距離度為對角元的對角矩陣。顯然，DQ（G）是實對稱的正矩陣，故由對稱矩陣與非負矩陣理論［8］可知，其特征值全為實數(shù)，并且最大特征值恰為DQ（G）的譜半徑ρ（G）。另外，最大特征值的代數(shù)重數(shù)為1，其對應的的特征向量中各分量符號一致，為方便起見，本文中將屬于ρ（G）的分量全正的單位特征向量稱為Perron向量。基于極圖理論研究的重要性，近年來，關于刻畫距離無符號拉普拉斯譜半徑極圖的研究也逐漸成為新的研究熱點。如：R.Xing和B.Zhou等［9-10］分別刻畫了n階樹、單圈圖、雙圈圖、二部圖、給定懸掛點的圖類以及給定連通度的圖類中距離無符號拉普拉斯譜半徑最小圖的結構；G.D.Yu等［11］研究了具有n-3個懸掛點的n階樹的距離無符號拉普拉斯譜半徑的極小值，并刻畫了一類n階具有n-3個懸掛點的樹的距離無符號拉普拉斯譜半徑的極小值和極大值；本文的第一作者［12-13］參與刻畫了給定染色數(shù)和含割點的圖類中距離無符號拉普拉斯譜半徑極小圖的結構；K.C.Das［14］等獲得了距離無符號拉普拉斯譜半徑關于獨立數(shù)的一個下界，并刻畫了相應的極圖；Wrong dein等［15］證明了M.Aouchiche和P.Hanse在文［7］中提出的關于距離拉普拉斯矩陣的最大和第二大特征值以及距離無符號拉普拉斯矩陣的第二大特征值的四個猜想。

受上述成果的啟發(fā)，本文研究了在含割邊的連通圖類中，距離無符號拉普拉斯譜半徑極小圖的結構，并在此基礎上，獲得了含割邊的n階連通圖的距離無符號拉普拉斯譜半徑的一個下界。

2　主要結果

設G為n階連通圖，V（G）=｛v1，v2，…，vn｝，對n維列向量 x=（x1，x2，…，xn）∈Rn，若建立映射 φ：V（G）→Rn，使得對任意的 i∈｛1，2，…，n｝，有xi=φ（vi），則x可視為定義在V（G）上的一個函數(shù)。不難發(fā)現(xiàn)，

若x是DQ（G）的對應于特征值λ的一個特征向量，則由特征值與特征向量的關系可知，x≠0且

對任意vi∈V（G）都成立，反之亦真。另外，由Rayleigh商理論［8］可知，對任意單位向量x∈Rn，

等式當且僅當x是DQ（G）的Perron向量時成立。

對于一個非負不可約矩陣而言，任一元素值的增大都將導致該矩陣譜半徑的變大，基于這一理論，我們易得下述引理。

引理 2.1［12］設G是一個連通的簡單圖，且u，v∈V（G），則

（1）若uv?E（G），則ρ（G）＞ρ（G+uv）；

（2）若 uv∈E（G）且 uv不是 G的割邊，則ρ（G）＜ρ（G-uv）。

圖G的距離無符號拉普拉斯譜半徑與圖G的頂點的最大距離度之間有以下不等式關系。引理

2.2［10］設G是一個連通圖，則Trmax（G）＜ρ（G）≤2Trmax（G）。

設v∈V（G），記v在G中的鄰域為N（v），則有，

引理2.3［12］設G是包含頂點u，v的連通圖，則

（1）若N（u）｛v｝=N（v）｛u｝，則Tr（u）=Tr（v）；

（2）若N（u）｛v｝?N（v）｛u｝，則Tr（u）＞Tr（v）。

由引理2.3，我們可以得到下述引理。

引理2.4［12］設G是包含頂點u，v的連通圖，x是DQ（G）的一個Perron向量。

（1）若N（u）｛v｝=N（v）｛u｝，則xu=xv；

（2）若N（u）｛v｝?N（v）｛u｝，則xu＞xv。

設G和H是分別含頂點u和v的兩個不相交的連通圖，在G的頂點u和H的頂點v之間添加一條邊，形成的圖，在本文中稱為G與H的（uv）連圖，記作G（u）?H（v）。為方便起見，將完全圖Kp與Kq的連圖記作G（p，q）。

定理2.5設G是含割邊的n階連通圖，則ρ（G）≥ρ（G（1，n-1）），等號當且僅當G=G（1，n-1）時成立。

證明 在所有含割邊的n階連通圖類中，設G的距離無符號拉普拉斯譜半徑最小，下面刻畫G的結構。

首先G一定只含一條割邊，設為uv。否則，若G含有兩條割邊e1和e2，則可以適當添加一些邊，使得e2不再是割邊，所得的圖記為G′，由引理2.1，ρ（G′）＜ρ（G），矛盾！

其次，同樣由引理2.1，G可視為兩個完全圖Kp與Kq的連圖G（p，q），其中p+q=n，u∈V（Kp），v∈V（Kq）。不妨設 p≤q，則一定有 p≥1 且p≠2。首先我們假設p≥3，記G（p，q）的距離無符號拉普拉斯譜半徑為ρ，對應的Perron向量為x。由于對任意的w1，w2∈V（Kp-u），N（w1）｛w2｝=N（w2）｛w1｝，故由引理2.4知，x的對應于Kp-u中所有頂點的分量一定相等，記為x1；同樣的道理，對應于Kq-v中所有頂點的分量也一定相等，記為x2；記u所對應的分量為xu，v所對應的分量為xv。則由（2）得：

即，

于是ρ一定是方程 fp，q（λ）=0的最大根，其中

考慮多項式 fp，q（λ）與 fp-1，q+1（λ）的差，經過一些簡單的計算，可得：

記G（p-1，q+1）的距離無符號拉普拉斯譜半徑為ρ′，則由引理2.2得，ρ′≤2p+6q，故

注意到 fp-1，q+1（ρ′）=0，于是得 fp，q（ρ′）＜0。根據(jù)ρ為多項式 fp，q（λ）的最大根以及知，ρ′＜ρ。綜合以上分析知，p=1，從而q=n-1。于是結論成立。

證明 由定理2.4，只需計算G（1，n-1）的距離無符拉普拉斯譜半徑。根據(jù)G（1，n-1）的結構，類似于前面的記號，用u表示懸掛點，其鄰點表示為v。記G（1，n-1）的距離無符號拉普拉斯譜半徑為ρ，對應的Perron向量為x，則x的對應于頂點u的分量為xu，對應于頂點v的分量為xv，由定理2.4知，x的對應于其余頂點的分量都相等，記為x0，則由（2）得：

即，

于是ρ一定是方程f（λ）=0的最大根，其中

利用定理2.6，可以進一步得出含割邊連通圖的距離無符號拉普拉斯譜半徑的一個下界。

推論2.7對任一含割邊的連通圖G，有ρ（G）≥2，其中等號當且僅當G=G（1，1）時成立。

［1］R.L.Graham H.O.Pollak.On the addressing problem for loop switching［J］.Bell Sys.Tech.J.1971，50（8）：2495-2519.

［2］M.Edelberg，M.R.Garey and R.L.Graham.On the distance matrix of a tree［J］.Discrete Math.1976，14（1）：23-29.

［3］R.L.Graham and H.O.Pollak.On embedding graphs in squashed cubes［J］.Lecture Notes in Mathematics，1972，303：99-110.

［4］R.L.Graham and L.Lovasz.Distance matrix polynomials of trees［J］.Adv.in Math.，1978，29（1）：60-88.

［5］H.Hosoya，M.Murakami，M.Gotoh.Distancepolynomialandcharacterizationofagraph［J］.Natur.Sci.Rep.OchanomizuUniv.，1973，24：27-34.

［6］D.H.Rouvray.The search for useful topological indices in chemistry［J］.Amer.Scientist，1973，61（6）：729-735.

［7］M.Aouchiche.P.Hansen，Two Laplacians for the distance matrix of a graph［J］.Linear Algebra Appl.，2013，439（1）：21-33.

［8］R.A.Horn，C.R.Johnson.Matrix Analysis［M］.Cambridge：Cambridge Univ.Press，1990.

［9］R.Xing，B.Zhou.On the distance and distance signless Laplacian spectral radii of bicyclic graphs［J］.Linear Algebra Appl.，2013，439（12）：3955-3963.

［10］R.Xing，B.Zhou，J.Li.OnthedistancesignlessLaplacianspectralradiusofgraphs［J］.LinearMultilinearAlgebra，2014，62：1377-1387.

［11］G.D.Yu，Q.J.Gong，L.Duan.The distance signless Laplacian spectral radius of trees with n-3 pendent vertices［J］.Journal of University of Science and Technology of China，2014，44（3）：176-180.

［12］X.X.Li，Y.Z.Fan，S.P.Zha.A lower bound for the distance signless Laplacian spectral radius of graphs in terms of chromatic number［J］.Journal of Mathematical Research with Applications，2014，34 （3）：289-294.

［13］李小新，查淑萍.含割點的連通圖的最小距離無符號aplace譜半徑［J］.中國科學技術大學學報，2014，44（12）：982-985.

［14］K.C.Das.Bounds on the entries of the principal eigenvector of the distance signless Laplacian matrix［J］.Linear Algebra Appl.，2015，483：200-220.

［15］F.L Tian，D.Wong，J，L Rou.Proof for four conjectures about the distance Laplacian and distance signless Laplacian eigenvalues of a graph［J］.Linear Algebra Appl.2015，471：10-20.

［責任編輯：桂傳友］

Minimum Distance Signless Laplacian Spectral Radius of Connected Graphs with Cut Edges

Zha Shuping，Li Luyao，Gao Fang
（College of Mathematics and Computer，Chizhou University，Chizhou Anhui 247000）

Among all the connected graphs on n vertices with cut edges，the unique graph with minimum distance signless Laplacian spectral radius is characterized by using the relations of eigenvalue and eigenvector.On this basis，a lower bound of the distance signless Laplacian spectral radius of connected graphs on vertices with cut edges is determined.

Graph；Cut Edge；Distance Signless Laplacian Matrix；Spectral Radius

O157

A

1674-1102（2016）03-0023-03

10.13420/j.cnki.jczu.2016.03.005

2016-03-21

安徽省高校優(yōu)秀青年人才支持計劃重點項目（gxyqZD2016367）；池州學院大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目（201411306124）。

查淑萍（1978-），女，安徽懷寧人，池州學院數(shù)學與計算機學院教師，碩士，研究方向為圖論及其應用。