單圈圖與雙圈圖補圖的Aα-譜半徑

張 榮,郭曙光

(鹽城師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,江蘇鹽城,224002)

§1 引言

本文僅討論有限無向簡單圖.G=(V(G),E(G))是n階連通圖,V(G)={v1,v2,……,vn}為其頂點集,E(G)為其邊集,dG(vi)表示圖G中頂點vi的度,A(G)為G的鄰接矩陣,D(G)為G的度對角矩陣.圖的無符號拉普拉斯矩陣被定義為Q(G)=D(G)+A(G).2017年,Nikiforov[1]提出并研究圖的Aα-矩陣,即圖G的度對角矩陣D(G)與鄰接矩陣A(G)的凸線性組合:

稱它的最大特征根為G的Aα-譜半徑,簡記為ρα(G).若G為連通圖,則Aα(G)是不可約的.根據(jù)非負(fù)矩陣的Perron-Frobenius定理,ρα(G) 的重數(shù)為1,并且存在唯一的正單位特征向量,稱之為ρα(G)的Perron向量.圖G的補圖Gc是指與G有相同頂點集的簡單圖,在Gc中兩個頂點相鄰當(dāng)且僅當(dāng)它們在G中不相鄰.

1986年,Brualdi和Solheid[2]提出了確定圖類鄰接譜半徑的界并刻畫極圖的問題.這類問題后來被稱為Brualdi-Solheid問題,被人們廣泛研究,并被移植到各種圖矩陣的譜半徑研究中,至今仍然是圖譜研究的熱點.2014年,Stevanovi′c的新著[3]對近十年來鄰接譜半徑(特別是Brualdi-Solheid問題)的研究成果,證明技巧進行了綜述,并提出一些值得進一步研究的猜想和待解決問題.2017年,Tait和Tobin[4]在n充分大的前提下證明了Brualdi-Solheid型問題的三個著名猜想,2018年,Bollobás等人[5]研究了d維超方體圖的m階導(dǎo)出子圖譜半徑的最大化問題.

圖的Aα-矩陣統(tǒng)一并推廣了鄰接矩陣與無符號拉普拉斯矩陣,對它的研究可將鄰接譜和無符號拉普拉斯譜的研究方法一般化,得到一般性的結(jié)果,因而成為近期圖譜研究的又一熱點.圖的Aα-譜半徑的Brualdi-Solheid問題更是受到研究者的廣泛關(guān)注.例如,Nikiforov[1]分別確定了色數(shù)給定和不含Kr+1(r ≥2)圖的Aα-譜半徑的可達上界.Nikiforov等[6]給出最大度給定的樹的Aα-譜半徑一個緊的上界.Nikiforov等[7]和Xue等[8]同時確定了直徑給定的圖的Aα-譜半徑最大的圖和團數(shù)給定的圖的Aα-譜半徑最小的圖.Lin等[9]分別確定了割點數(shù)給定的連通圖和匹配數(shù)給定的樹的Aα-譜半徑最大的圖.Li等[10]分別確定了給定度序列的n階樹和單圈圖的Aα-譜半徑最大的圖.Yu等[11]給出了不含K2,t(t ≥3) minor的圖Aα-譜半徑可達上界,并確定了具有最大Aα-譜半徑的唯一的外平面圖.Chen等[12]給出了一個圖的二次冪圖的Aα-譜半徑的上界和下界,并確定了樹的二次冪圖的Aα-譜半徑前三大的圖.

邊數(shù)等于頂點數(shù)加c-1的簡單連通圖稱為c圈圖.當(dāng)c=0,1,2,3 時,分別稱之為樹,單圈圖,雙圈圖,三圈圖.Liu等[13]給出了n階單圈圖的補圖的鄰接譜半徑的上界,并刻畫了唯一的達到該上界的極圖.Yin等[14]給出了n階三圈圖的補圖的鄰接譜半徑的上界,并刻畫了唯一的達到該上界的極圖.本文研究單圈圖與雙圈圖補圖的Aα-譜半徑,分別確定n階單圈圖與雙圈圖補圖的Aα-譜半徑的上界,并刻畫相應(yīng)的極圖.

§2 記號與引理

用Cn表示n個頂點的圈,Pn表示n個頂點的路,Kn表示n個頂點的完全圖,Nn表示n個頂點的空圖,NG(v)表示圖G中鄰接于v的頂點組成的集合.G的懸掛頂點是指度為1的頂點,與懸掛頂點相關(guān)聯(lián)的邊稱為懸掛邊.若S ?V(G),用G[S]表示圖G的由S導(dǎo)出的子圖.兩個圖G1=(V1,E1)和G2=(V2,E2)(V1∩V2=?)的直和是指圖G=G1∪G2,其中V(G)=V1∪V2,E(G)=E1∪E2.圖G1=(V1,E1)與G2=(V2,E2)的完全積記為G1▽G2,是指把G1∪G2中的V1的每一個頂點分別與V2的每一個頂點連接所得到的圖.設(shè)x=(x1,x2,……,xn)T為n維單位實列向量,根據(jù)Rayleigh’s準(zhǔn)則[15]知

其中等號成立當(dāng)且僅當(dāng)x為對應(yīng)于ρα(G)的特征向量.

引理2.1[7-8]設(shè)α ∈[0,1),G為連通圖,u,w是G的兩個頂點,uvi ∈E(G)且wvi/∈E(G)(i=1,2,……,k).設(shè)x=(x1,x2,……,xn)T為對應(yīng)于ρα(G)的Perron向量.令G*為從G中刪除邊uvi并加上邊wvi(i=1,2,……,k)得到的圖.若xw ≥xu,則ρα(G*)＞ρα(G).

引理2.2[16]設(shè)0≤α ≤1,G是一個圖,S ?V(G)且|S|=k.若對任意w ∈S,有dG(w)=d且對任意u,v ∈S滿足N(v){u}=N(u){v},則有下面的結(jié)論成立.

(1) 如果G[S]是一個團,則(d+1)α-1是Aα(G)的一個特征值,其重數(shù)至少為k-1.

(2) 如果G[S]是一個獨立集,則dα是Aα(G)的一個特征值,其重數(shù)至少為k-1.

下面的引理是引理2.1的一個推論,它是主要結(jié)果證明的關(guān)鍵.

根據(jù)引理2.3,可證明下列引理.

引理2.4設(shè)uv是圖G的一條非懸掛邊的割邊,并且Gc也是連通圖,記收縮邊uv成一點w并在點w接出一條懸掛邊所得的圖為G*(如圖1所示),則ρα(Gc)＜ρα(G*c).

圖1 G,G*

設(shè)G1,G2為兩個連通圖,u1,u2分別是它們的頂點.將G1中的頂點u1和G2中的頂點u2粘合成一個頂點,所得的圖記為G1u1u2G2(簡記為G1G2).特別地,GTn(如圖2所示)表示將圖G的一個頂點與一棵n階樹Tn的一個頂點粘合所得圖.GK1,n-1(如圖2所示)將圖G的一個頂點與K1,n-1的中心粘合所得的圖.

圖2 GTn,GK1,n-1

§3 單圈圖補圖的Aα-譜半徑

綜合引理3.1和引理3.2,可以得到下述結(jié)論.

定理3.1設(shè)0≤α ＜1,圖G為n階單圈圖,則

§4 雙圈圖補圖的Aα-譜半徑

用B(n)表示所有n階雙圈圖組成的集合.令Ck,Cl是兩個頂點不相交的圈,v1是Ck的一個頂點,vs是Cl的一個頂點.把v1和vs用長為s-1 (s ≥1)的路v1v2……·vs連接起來所得到的圖稱為∞-圖(如圖3所示),其中s=1表示把v1,vs重合到一起.令Pl+1,Pp+1,Pq+1(l,p,q ≥1)是三條頂點不相交的路,并且其中至多有一條路的長為1.把這三條路的起始頂點和終點分別重合到一起所得到的圖稱為θ-圖(如圖3所示).雙圈圖可分為兩類,一類記為Bn,1,其中的圖要么是一個n階∞-圖,要么是在∞-圖的某些頂點接出一些樹得到的n階圖;另一類記為Bn,2,其中的圖要么是一個n階θ-圖,要么是在θ-圖的某些頂點接出一些樹得到的n階圖.

圖3 ∞-圖, θ-圖

設(shè)B1與B2是如圖4所示的兩個n階雙圈圖.當(dāng)n ＞5時,不難看出,除B1和B2之外,其它所有n階雙圈圖的補圖均為連通圖.當(dāng)n ＞5時,類似于單圈圖補圖的Aα-譜半徑的證明過程,可以得到如下結(jié)論.當(dāng)n=5 時通過直接計算驗證如下結(jié)論成立.

圖4 B1, B2

引理4.1設(shè)0≤α ＜1,G ∈Bn,1,則ρα(Gc)≤ρα(B1c),其中等號成立當(dāng)且僅當(dāng)G～=B1.

引理4.2設(shè)0≤α ＜1,G ∈Bn,2,則ρα(Gc)≤ρα(B2c),其中等號成立當(dāng)且僅當(dāng)G～=B2.

對于n階雙圈圖,在引理4.1和引理4.2的基礎(chǔ)上,可以證明下述定理.

致謝衷心感謝審稿人的意見和建議.