具有k個懸掛點(diǎn)的單圈圖的Aα-譜半徑

李夢霞，耿顯亞

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001）

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

本文考慮的是有限無向簡單圖.G=(V，E)是由n= |V|個頂點(diǎn)和m= |E|條邊組成.設(shè)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)就等價(jià)于無符號拉普拉斯矩陣Q(G).用ρα(G)表示矩陣Aα(G)的最大特征值，即圖G的Aα-譜半徑.在圖G中，與點(diǎn)v相鄰的點(diǎn)的集合稱為點(diǎn)v的鄰域，記作NG(v)（在沒有歧義的情況下，下標(biāo)可以省略）.與點(diǎn)v相關(guān)聯(lián)的邊的個數(shù)稱為點(diǎn)v的度，記作dG(v).顯然，dG(v)= |NG(v)|.Γn，k表示有n個頂點(diǎn)和k個懸掛點(diǎn)的所有樹集，樹Tn，k是通過在星圖K1，k上添加k條長度不超過2的懸掛邊得到的.用Cn，Pn分別定義有n的點(diǎn)的圈和路.邊數(shù)等于點(diǎn)數(shù)的連通圖稱為單圈圖.顯然一個單圈圖要么是一個獨(dú)立的圈，要么是由圈和與圈相連的樹構(gòu)成.用Un(k)定義有n個頂點(diǎn)和k個懸掛點(diǎn)的所有單圈圖集，用表示在圈C3上添加k條長度不超過2的懸掛邊，使該單圈圖有n個頂點(diǎn)和k個懸掛點(diǎn).本文考慮有k個懸掛點(diǎn)的所有單圈圖，確定了具有最大Aα-譜半徑的圖.

1 主要引理

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

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

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

2 重要結(jié)論

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

證明假設(shè)度數(shù)大于等于3的頂點(diǎn)個數(shù)為t：

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

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

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

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

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

圖1 圖G與圖

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

第一步，證明圖G上只有頂點(diǎn)v1上附著樹T.假設(shè)存在點(diǎn)vi上附著一個樹(v1≠vi)，vi是圈Cp上的點(diǎn).設(shè)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上的點(diǎn).那么，s≥1，t≥2.如果x1≥xi，設(shè)G'=G-{viz1…vizs}+{v1z1…v1zs}.如果x1＜xi，設(shè)G'=G-{v1ω1…v1ωt}+{viω1…viωt}.因?yàn)镚'∈Un(k)，根據(jù)引理1，得到ρα(G)＜ρα(G')，矛盾.因此，圖G只有一個附著樹.

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

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

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

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

通過上述證明，得到當(dāng)G=時(shí)，單圈圖具有最大Aα-譜半徑.證明結(jié)束.

3 總結(jié)

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