圍長給定雙圈圖的Aα-譜半徑的上界

葉藹云

1.青海師范大學 數學與統計學院，青海 西寧 810008；2.鹽城師范學院 數學與統計學院，江蘇 鹽城 224002

設G=(V(G)，E(G))為n階簡單無向圖，頂點集V(G) ={v1，v2，…，vn}（n∈?），邊集E(G) ={e1，e2，…，em}(m∈?)，記圖G的鄰接矩陣和度對角矩陣分別為A(G)、D(G)，定義圖G的無符號拉普拉斯矩陣Q(G) =D(G) +A(G)，稱矩陣A(G)、Q(G)的最大特征值分別為圖的譜半徑和無符號拉普拉斯譜半徑。2017年，Nikiforov［1］定義圖G的Aα-矩陣為

圖G的Aα-矩陣可以看作是圖G的鄰接矩陣和無符號拉普拉斯矩陣的共同推廣，其最大特征值稱為圖G的Aα-譜半徑，記作ρα(G)。

圖的Aα-矩陣的概念一經提出就迅速引起了國內外學者的關注，其中最受學者關注的問題是：對給定的圖類尋求其Aα-譜半徑的界并且刻畫達到界的極圖，這也是Brualdi-Solheid 問題在Aα-矩陣上的推廣。2017 年，Nikiforov 等［2］給出最大度給定的樹的Aα-譜半徑一個緊的上界；2018年，Nikiforov 等［3］和Xue 等［4］同時確定了直徑給定圖的Aα-譜半徑最大的圖和團數給定圖的Aα-譜半徑最小的圖；同年，Lin 等［5］分別確定了頂點數和割點數給定圖的Aα-譜半徑最大的圖，頂點數和匹配數給定樹的Aα-譜半徑最大的圖；2021 年，Li 等［6］分別刻畫了時，邊數給定、團數和邊數給定以及色數和邊數給定圖的最大Aα-譜半徑的極圖。

雙圈圖是邊數等于頂點數加1 的簡單連通圖，圖G的圍長是指G中最短圈的圈長，Wang等［7］確定了圍長為g的n階雙圈圖的譜半徑的上界和極圖；Li 等［8］和Zhu［9］分別獨立確定了圍長為g的n階雙圈圖的無符號拉普拉斯譜半徑點數的上界和極圖。本文確定了時，圍長為g的n階雙圈圖Aα-譜半徑的上界和極圖，推廣已有的成果。

1 記號與引理

用Cn表示n個頂點的圈、Pn表示n個頂點的路、Sn表示n個頂點的星圖，對于圖G，dG(vi)表示頂點vi的度，N(vi)表示頂點vi的鄰接點集，圖G-uv為從G中刪去邊uv∈E(G)所得的圖，G+uv為在G中添加一條邊uv（u，v∈V(G)，uv?E(G)）所得的圖。圖G的懸掛頂點是指度為1 的頂點，懸掛邊是指與懸掛頂點相關聯的邊。若G為連通圖，則Aα(G)是不可約的，根據非負矩陣的Perron-Frobenius 定理，ρα(G)的重數為1，并且存在唯一的正單位特征向量X=(x1，x2，…，xn)T，此向量稱為Aα(G)的Perron向量。

設Cz、Ct是兩個頂點不相交的圈（z、t是正整數，且z、t≥3，分別表示Cz、Ct的圈長。不失一般性，假定z≥t），v1是Cz的一個頂點，vl是Ct的一個頂點，B1(z，l，t)表示Cz、Ct通過長為l- 1(l≥1)的路v1v2…vl連接而成的圖（見圖1，當l= 1 時，圖1中的v1、vl將粘合成一點）。設Pp+1、Pq+1、Pr+1是3個頂點不相交的路（p、q、r是正整數，分別表示Pp+1、Pq+1、Pr+1的路長，且至多有一條路的長為1，因此假定r≥q≥p≥1），B2(p，q，r)表示將這3 條路的始點和終點粘合而得到的圖（圖2）。

圖1 B1(z，l，t)Fig. 1 B1(z，l，t)

圖2 B2(p，q，r)Fig. 2 B2(p，q，r)

在B1(z，l，t)、B2(p，q，r)的某些頂點接出一些樹形成的雙圈圖，分別稱為第一類雙圈圖和第二類雙圈圖，同時稱B1(z，l，t)、B2(p，q，r)為雙圈圖的基圖，并用B(n，g)表示所有圍長為g的n階雙圈圖所構成的集合，B1(n，g)表示第一類型中圍長為g的n階雙圈圖所構成的集合，B2(n，g)表示第二類型中圍長為g的n階雙圈圖所構成的集合，B1*(z，l，t)表示在B1(z，l，t)的4 度頂點上接出一些懸掛邊所得的n階雙圈圖，B2*(p，q，r)表示在B2(p，q，r)的某個3 度頂點上接出一些懸掛邊所得的n階雙圈圖，B22*(p，q，r)表示在B2(p，q，r)的某個2 度頂點上接出一些懸掛邊所得的n階雙圈圖。

引理1［2-3］設α∈[0，1) ，G為連通圖，u、w是G的兩個頂點，uvi∈E(G) 且wvi?E(G)(i=1，2，…，k，k≤n)，X=(x1，x2，…，xn)T為對應ρα(G)的Perron向量，G′為從G中刪除邊uvi并加上邊wvi得到的圖。若xw≥xu，則ρα(G) ＜ρα(G′)。

由引理1容易得到下面的推論。

推論1設e=uv是連通圖G的非懸掛邊，N(u) ∩N(v) = ?，在G-uv中粘合頂點u和v，得到的新頂點仍記為頂點u，在u點接出一條懸掛邊所得到的圖記為G′，若α∈[0，1) ，則ρα(G) ＜ρα(G′)。

引理2［1］設G為n階圖，其最大度為Δ，若，則ρα(G) ≥αΔ+，當且僅當且G=Sn時等式成立。

引理3［1］設G是沒有孤立頂點的通圖，若α∈[0，1) ，則

引理4設，n≥2g- 1，則

下面分兩種情形證明引理4。

情形1：g= 3。

證明：g= 3 時，根據n≥2g- 1，n取最小值5。

根據對稱性，不妨設x2≥x4，則

根據引理1，得到

情形2：g≥4。

證明：令h=n- 2g+ 1，根據引理3，可得

根據引理2，可得

由于n≥2g- 1，g≥4，不難驗證

從而

2 主要結果

通過研究圍長為g的n階雙圈圖的Aα-譜半徑，可以證明如下定理。

定理1設α∈[0，1) ，G∈B1(n，g)，則ρα(G) ≤，當且僅當時等號成立。

證明：由于G∈B1(n，g)，設G為B1(n，g)中Aα-譜半徑最大的圖，B1(p，1，q)為G的基圖，則q=g、p≥g、l≥1。

設X=(x1，x2，…，xn)T是Aα(G)的Perron 向量（xi對應頂點vi，i= 1，2，…，n），v1v2…vl為G中連接圈Cp和Cq的路，假設l≥2，并對邊v1v2應用推論1，可得圖G′∈B1(n，g)使得ρα(G) ＜ρα(G′)，這與假設G為B1(n，g)中Aα-譜半徑最大的圖矛盾。因此，l= 1，即V(Cp) ∩V(Cq) ={v1}。

設G中的圈Cp=v1v2…vpv1，假設p≥g+ 1，并對邊v1v2應用推論1，可得圖G′∈B1(n，g)使得ρα(G) ＜ρα(G′)，這與假設G為B1(n，g)中Aα-譜半徑最大的圖矛盾。因此，p=g，即G是在B1(g，1，g)的某些頂點處接出樹所得到的圖。

現在證明G中在B1(g，1，g)上接出的樹都是星。假設在B1(g，1，g)的某個頂點vi處接出的樹Ti不是星，則Ti中存在非懸掛邊vivj；對邊vivj應用推論1，可得G′∈B1(n，g)使得ρα(G) ＜ρα(G′)，這與假設G為B1(n，g)中Aα-譜半徑最大的圖矛盾。因此，G中在B1(g，1，g)上接出樹都是星。

現在證明G是在B1(g，1，g)的頂點v1處接出星所得到的圖。假設在B1(g，1，g)的兩個頂點vi、vj上分別接出星Si和Sj，不妨設xi≥xj，令

不難看出G′∈B1(n，g)，由引理1 可知ρα(G) ＜ρα(G′)，這與假設G為B1(n，g)中Aα-譜半徑最大的圖矛盾。因此，G是在B1(g，1，g)的某一個頂點vi上接出星所得到的圖。

現在證明G是在B1(g，1，g)的頂點v1處接出星所得到的圖。若i≠1，對頂點v1和vi應用引理1，可得，這與假設G為B1(n，g)中Aα-譜半徑最大的圖矛盾。因此，G是在B1(g，1，g)的頂點v1處接出星所得到的圖。

定理2設1，則，當且僅當時等號成立。

證明：由于G∈B2(n，g)，設G為B2(n，g)中Aα-譜半徑最大的圖，B2(p，q，r)為G的基圖，其中1 ≤p≤q≤r，則p+q=g。

設X=(x1，x2，…，xn)T是Aα(G) 的Perron 向量，其中xi對應頂點vi，i= 1，2，…，n。假設r≥q+ 1，因為p至少為1，且q不為1，所以q≥2，故r≥3。設Pr+1( =u) =v1v2…vr+1( =v)，對邊v1v2運用推論1，可得圖G′∈B2(n，g)使得ρα(G) ＜ρα(G′)，這與假設G為B2(n，g)中Aα-譜半徑最大的圖矛盾。因此，r=q，G是在B2(p，q，q)的某些頂點處接出樹所得到的圖。

現在證明G是B2(p，q，q)或G是在B2(p，q，q)的某一頂點vi處接出一些懸掛邊所得到的圖。

假設G=B2*2(p，q，q)，分兩種情形討論。

情形1：q-p≤1。

由于p+q=g，故，又r=q，故G=。 設，因，則y≥2，G是在的某個2度點處接出y條懸掛邊所得到的圖。

由引理2可得

再由引理3，可得

情形2：q-p≥2。

由于p+q=g，故，又r=q，故。 設z=n-p- 2q+ 1，因n≥，故z≥1，G是在B2(p，q，q)的某個2 度點處接出z條懸掛邊所得的圖。

由引理2可得

再由引理3，可得

由于p+q=g、q≥+ 1，從而

當z取最大值時，

從而

這與假設G為B2(n，g)中Aα-譜半徑最大的圖矛盾。

綜合情形1、情形2，可以得到G=B2(p，q，q)或(p，q，q)。

現在證明q-p≤1時，

假設q-p≥2，則G=B2(p，q，q)或G是在B2(p，q，q)的某個3 度點處接出一些懸掛邊所得到的圖。這里雙圈圖G的基圖頂點數為g+q- 1，若G=B2(p，q，q)，圖G是沒有懸掛點且頂點n=g+q- 1，則z=n-p- 2q+ 1 =n-g-q+ 1 = 0；若G是在B2(p，q，q)的某個3 度點處接出一些懸掛邊所得的圖，為了保證有懸掛點，圖G的頂點數n≥g+q，則z=n-p- 2q+1 =n-g-q+ 1 ≥1。

綜合以上討論z≥0。

由引理2可得

再由引理3，可得

當z取最大值時，

從而

這與假設G為B2(n，g)中Aα-譜半徑最大的圖矛盾。因此，q-p≤1。

定理3G是圍長為g的n階雙圈圖，設，則

由于B(n，g) =B1(n，g) ∪B2(n，g)，由引理4和定理1、定理2容易得到定理3的結論。