具有k個懸掛點的單圈圖的Aα-譜半徑

李夢霞，耿顯亞

（安徽理工大學 數學與大數據學院，安徽 淮南 232001）

當前，圖的Aα-矩陣引起了學者的廣泛關注，成為研究的熱點.Nikiforov［1］等刻畫了在所有n階連通圖中，Aα-譜半徑最小的圖.Xue［2］等刻畫了在Aα-譜半徑上的三種邊變換方法.作為應用，Nikiforov［3］等和Xue等獨立確定了給定直徑的圖中Aα-譜半徑最大的圖和給定團數的圖中Aα-譜半徑最小的圖.Lin［4］等給出了有關Aα(G)矩陣特征值的一些性質.關于一個圖能否由其Aα-譜半徑確定的研究才剛剛開始.Lin［5］等證明了在一定條件下，有一些圖可以由其Aα-譜半徑確定.關于Aα-譜半徑的更多成果參考文獻［6-8］.Guo［9］等刻畫了有k個懸掛點的所有單圈圖和雙圈圖中譜半徑最大的圖，Wu［10］等確定了有k個懸掛點的樹中譜半徑最大的圖.

本文考慮的是有限無向簡單圖.G=(V，E)是由n= |V|個頂點和m= |E|條邊組成.設A(G)，D(G)分別是圖G的鄰接矩陣和度對角矩陣.圖G的無符號拉普拉斯矩陣被定義為Q(G)=D(G)+A(G).對于任意的α∈[0，1]，Nikiforov［11］提出了矩陣Aα(G)=αD(G)+(1-α)A(G).容易看出，A0(G)=A(G)，并且(G)=2Q(G)，因此(G)就等價于無符號拉普拉斯矩陣Q(G).用ρα(G)表示矩陣Aα(G)的最大特征值，即圖G的Aα-譜半徑.在圖G中，與點v相鄰的點的集合稱為點v的鄰域，記作NG(v)（在沒有歧義的情況下，下標可以省略）.與點v相關聯的邊的個數稱為點v的度，記作dG(v).顯然，dG(v)= |NG(v)|.Γn，k表示有n個頂點和k個懸掛點的所有樹集，樹Tn，k是通過在星圖K1，k上添加k條長度不超過2的懸掛邊得到的.用Cn，Pn分別定義有n的點的圈和路.邊數等于點數的連通圖稱為單圈圖.顯然一個單圈圖要么是一個獨立的圈，要么是由圈和與圈相連的樹構成.用Un(k)定義有n個頂點和k個懸掛點的所有單圈圖集，用表示在圈C3上添加k條長度不超過2的懸掛邊，使該單圈圖有n個頂點和k個懸掛點.本文考慮有k個懸掛點的所有單圈圖，確定了具有最大Aα-譜半徑的圖.

1 主要引理

引理1設u，v是連通圖G上的兩個頂點，N?V(v)(N(u)∪{u})，且x是ρα(G)的對應單位特征向量.假設G'=G-{vω：ω∈N}+{uω：ω∈N}，如果N≠?且xu＞xv，那么，ρα(G)＜ρα(G')，m(G)=m(G').［2，3］

引理2設u是連通圖G上的一個頂點且d(u)≥2，新圖Gp，q(u)是通過在點u上連接兩條長為p和q的路得到的.假設α∈[0，1)，如果p-q≥2，則ρα(Gp，q(u))≤ρα(Gp-1，q+1(u)).［12］

引理3設G是一個連通圖，uv是圖G內部路中的邊.圖Guv表示在邊uv上添加一個點ω使uv=uω+vω，那么，ρα(Guv)＜ρα(G)，這里α∈[0，1).［12］

2 重要結論

定理1假設T是有n個頂點和k個懸掛點的樹，如果α∈[0，1)，那么，ρα(T)≤ρα(Tn，k)，當且僅當T=Tn，k時等式成立.

證明假設度數大于等于3的頂點個數為t：

情況1：t=0.T是一條長為n的路，因此，T=Tn，2，則ρα(T)=ρα(Tn，2)

情況2：t=1.根據引理2，容易證明T=Tn，k時等式成立.

情況3：t＞1.假設X={x1x2…xn}是樹T的單位特征向量，其中xi對應vi(1≤i≤n).設u，v是T上度數大于等于3的兩個頂點，且xu≥xv.由于在點u，v間有一條路，所以設在該路上與v相鄰的點為ω.假設，顯然，T1'仍然有k個懸掛點.根據引理1，得到ρα(T)≤ρα(T1')并且度數大于等于3的頂點個數變為t-1.

如果t-1＞1，將樹T1'重復做以上變形，直到個數變為1，從而得到樹T2'，T3'…Tt'-1.根據引理1得到ρα(T2')＜ρα(T3')＜…＜ρα(Tt'-1).根據情況2，得到ρα(Tt'-1)≤ρα(Tn，k)，因此，ρα(T)＜ρα(Tn，k).證明結束.

定理2假設G是有n個頂點和k個懸掛點的單圈圖，如果α∈[0，1)，那么，，當且僅當G=時等式成立.（見圖1）

圖1 圖G與圖

證明設G∈Un(k)，V(G)={v1v2…vn}，對應單位特征向量X={x1x2…xn}，其 中xi對應vi(1≤i≤n).

第一步，證明圖G上只有頂點v1上附著樹T.假設存在點vi上附著一個樹(v1≠vi)，vi是圈Cp上的點.設N(vi)={vi-1，vi+1，z1…zs}，N(v1)={vj-1，vj+1，ω1…ωt}，其中，vi-1，vi+1，vj-1，vj+1都是圈Cp上的點.那么，s≥1，t≥2.如果x1≥xi，設G'=G-{viz1…vizs}+{v1z1…v1zs}.如果x1＜xi，設G'=G-{v1ω1…v1ωt}+{viω1…viωt}.因為G'∈Un(k)，根據引理1，得到ρα(G)＜ρα(G')，矛盾.因此，圖G只有一個附著樹.

第二步，證明樹T上所有頂點的度都不超過2.假設vi是T上的一點且d(vi)＞2.令N(vi)={z1…zt}，N(v1)={ω1…ωs}，假 設z1，ω3是 路v1vi上 的 點且ω1∈Cp，ω2∈Cp.如果x1≥xi，設G'=G-{viz3…vizt}+{v1z3…v1zt}.

如果x1＜xi，設G'=G-{v1ω1，v1ω4…v1ωs}+{viω1，viω4…viωs}.因為G'∈Un(k)，根據引理1，得到ρα(G)＜ρα(G')，矛盾.因此，樹T上所有頂點的度都不超過2.

第三步，證明附著在點v1上的k條懸掛路是幾乎等長的（長度不超過2）.根據定理1很容易看出.

第四步，證明圈Cp長為3.假設p≥4.設Cp=v1v2…vpv1，顯然G≠Cp，v1v2…vpv1是一條封閉的內部路.設G'=G-{v2v3，v3v4}+{v2v4}，那么，G'∈Un(k).通過引理3，得到ρα(G)＜ρα(G')，矛盾.因此，p=3.

通過上述證明，得到當G=時，單圈圖具有最大Aα-譜半徑.證明結束.

3 總結

本文證明了當T=Tn，k時，樹具有最大Aα-譜半徑，分析了有k個懸掛點的所有單圈圖，確定了具有最大Aα-譜半徑的圖.這為接下來關于Aα-譜半徑的更多研究提供了思路.