給定最小度和邊連通度的圖的最大無符號拉普拉斯譜半徑

方 怡，余桂東

（1.銅陵職業技術學院，安徽銅陵244061；2.合肥幼兒師范高等專科學校，安徽合肥230013；3.安慶師范大學數理學院，安徽安慶246133）

本文所討論的圖均為有限簡單無向圖，設G=(V(G),E(G))是一個n階簡單連通圖，其頂點集V(G)={v1,v2,v3,…,vn}，頂點v∈V(G)的鄰域定義為NG(v)={u：uv∈E(G)}，頂點v的度dG(v)=|NG(v)|且N[v]=N(u)∪{v}。G的最小度記為δ(G)，如果A、B是V(G)中互不相交的子集，則[A,B]={uv∈E(G)|u∈A,v∈B}。

S是V(G)的一個子集，設N(S)=∪v∈SN(v)且G[S]是由S產生的G的導出子圖。如果圖G中任意兩點均有一條路連接，則稱圖G是連通的。假設U?E(G)，如果G-U是不連通的，則稱U是G的一個邊割。G的邊連通度定義為k′(G)或k′，是G的邊割的最小基數。很明顯，k′≤δ。

圖G的度對角矩陣為D(G)=diag(dG(v1),dG(v2),dG(v3),…,dG(vn))。圖G的鄰接矩陣定義為A(G)=(aij)n×n，其中當vi、vj相鄰時，aij=1，否則aij=0。圖G的無符號拉普拉斯矩陣定義為Q(G)=D(G)+A(G)。由于A(G)為實對稱矩陣，故其特征值均為實數，可進行排序，我們稱A(G)的最大特征值為圖G的譜半徑，記為μ(G)；稱Q(G)的最大特征值為圖G的無符號拉普拉斯譜半徑，記為q(G)。與μ(G)對應的全正向量稱為G的Perron向量。

近年來，關于圖的譜半徑和無符號拉普拉斯譜半徑的研究取得了許多有意義的成果，特別是在給定的一類圖中尋找最大的譜半徑和無符號拉普拉斯譜半徑[1-4]。文獻[4]報道了在有n個頂點、最小度為δ且邊連通度k′＜δ這一類圖中找譜半徑最大的圖的方法，受此啟發，本文主要研究有n個頂點、最小度為δ且邊連通度k′＜δ這一類圖中無符號拉普拉斯譜半徑最大的圖。設是一個階為n、最小度為δ且邊連通度為k′的}圖，其中n≥2,δ≥k′≥0。

在給出主要結論之前，先介紹一些引理和特殊符號。

對于一個圖G，不必是連通的。對于圖G的點集V(G)定義這兩個符號≥G和～G：

u≥Gv當且僅當N(u){v}?N(v){u}，u～Gv當且僅當N(u){v}=N(v){u}。

如果N(u){v}?N(v){u}，則記作u＞Gv，?表示嚴格包含。

引理1[5]設G是最小度為δ的圖，U是V(G)的非空真子集，如果|[U,VU]|≤δ-1，則|U|≥δ+1。

引理2[6]設G是連通圖，G′是G的一個真子圖，則q(G)′＜q(G)。

引理3[7]設u、v是連通圖G中兩個不同的點，x是Q(G)的Perron向量。

（1）如果u＞Gv，則xu＞xv；

（2）如果u～Gv，則xu=xv。

引理4[8]設G是連通圖，其中u、v是G的兩個點。假設v1,v2,v3,…,vs∈N(v)N(u)(1≤s≤dG(v))且x=(x1,x2,x3,…,xn)T是Q(G)的Perron向量，其中xi與點vi(1≤i≤n)相對應。設G*是通過在G中刪除vvi邊添加uvi邊獲得的，1≤i≤s。如果xu≥xv，則q(G)＜q(G*)。

引理5[9]設G=(V,E)是一個n階圖，則，當且僅當x是q(G)對應的特征向量時，等式成立。

定理1如果在這一類圖中G0的無符號拉普拉斯譜半徑最大，其中1≤k′＜δ，則，其中是從Kδ+1和Kn-δ-1之間加入k′條邊獲得的圖。

證明設G0是中的圖，滿足是q(G0)的Perron向量。設U=[A,B]是一個邊割，滿足|U|=k′。根據引理1，δ+1≤|A|≤n-δ-1，δ+1≤|B|≤nδ-1。設v0是度為δ的點，不失一般性，假設v0∈A，NG0[A](v0)={v1,v2,v3,…,vs}和NG0[B](v0)={vs+1,vs+2,vs+3,…,vδ}。由引理2可知G0[A]-v0和G0[B]都是團。

由引理2和1≤k′＜δ的條件知，要證明，只 須 證 明min{|A|,|B|}=δ+1。假 設min{|A|,|B|}≥δ+2，則有下面2個斷言。

斷言1對A{v0}（或B）中任一對點u和v，則xu≥xv當且僅當N(u){v}?N(v){u}。

證明根據引理3中的條件（1）可知，充分性是成立的。

下面證明必要性：假設u和v是A{v0}中的點且滿足xu≥xv，但是，則存在點p∈N(v){u}，但p?N(u){v}。假設p∈B，令H=G0-pv+pu。由于min{|A|,|B|}≥δ+2，G0[A]-v0和G0[B]都是團，我們得到δ(H)=δ且U{pv}∪{pu}是H的一個滿足最小基數的邊割。因此，H。結合引理4可得，q(H)＞q(G0)，這與G0的選擇矛盾。

因此，假設p∈A且。因為G0[A]-v0是一個團，得到p=v0。現在設H′=G0-v0v+v0u，則H。結合引理4可得，q(H)＞q(G0)，這與G0的選擇矛盾。因此，對于A{v0}中的一對點u和v，xu≥xv總是表示。根據引理3中條件（2）可知，當N(u){v}=N(v){u}時xu=xv。于是若xu＞xv，則有N(u){v}?N(v){u}。通過相似的討論，也可以證明在B中的一對點u和v也是滿足上述情況的。

斷言2[AN[v0],B]=?。

證明假設[AN[v0],B]≠?。設u∈AN[v0]和v∈B是兩個點，且滿足uv∈[AN[v0],B]。注意對于1≤i≤s，v0∈N(vi)且v0?N(u)，又根據斷言1，N(vi){u}?N(u){vi}，1≤i≤s。由于v∈N(u){vi}，得到v∈N(vi)，其中1≤i≤s，進而可得|[A,B]|≥(δ-s)+s+1=δ+1，這與|[A,B]|=k′＜δ矛盾。

現在定義集合A′是由AN[v0]中任意取|A|-δ-1個點組成，集合B′是由BN(A)中任意取|B|-δ-1個點組成。根據斷言2和B′的選擇知道[A′,B]=[A,B′]=?。由于min{|A|,|B|}≥δ+2且|[A,B]|=k′＜δ，有|A′|≥1,|B′|≥1。現考慮以下兩種情況：

情況1

在這種情況下，設H是從G0中去掉[A′,A-A′]中所有邊且增加G0[A-A′]和G0[A′∪B]中所有可能的邊得到的，這樣H[A-A′]和H[A′∪B]都是團，則，結合引理5可得

這與G0的選擇矛盾。

情況2

這與G0的選擇矛盾。