国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2023-11-18 03:05:36葉藹云
關(guān)鍵詞:上界情形頂點(diǎn)

葉藹云

1.青海師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,青海 西寧 810008;2.鹽城師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,江蘇 鹽城 224002

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

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

圖的Aα-矩陣的概念一經(jīng)提出就迅速引起了國內(nèi)外學(xué)者的關(guān)注,其中最受學(xué)者關(guān)注的問題是:對(duì)給定的圖類尋求其Aα-譜半徑的界并且刻畫達(dá)到界的極圖,這也是Brualdi-Solheid 問題在Aα-矩陣上的推廣。2017 年,Nikiforov 等[2]給出最大度給定的樹的Aα-譜半徑一個(gè)緊的上界;2018年,Nikiforov 等[3]和Xue 等[4]同時(shí)確定了直徑給定圖的Aα-譜半徑最大的圖和團(tuán)數(shù)給定圖的Aα-譜半徑最小的圖;同年,Lin 等[5]分別確定了頂點(diǎn)數(shù)和割點(diǎn)數(shù)給定圖的Aα-譜半徑最大的圖,頂點(diǎn)數(shù)和匹配數(shù)給定樹的Aα-譜半徑最大的圖;2021 年,Li 等[6]分別刻畫了時(shí),邊數(shù)給定、團(tuán)數(shù)和邊數(shù)給定以及色數(shù)和邊數(shù)給定圖的最大Aα-譜半徑的極圖。

雙圈圖是邊數(shù)等于頂點(diǎn)數(shù)加1 的簡單連通圖,圖G的圍長是指G中最短圈的圈長,Wang等[7]確定了圍長為g的n階雙圈圖的譜半徑的上界和極圖;Li 等[8]和Zhu[9]分別獨(dú)立確定了圍長為g的n階雙圈圖的無符號(hào)拉普拉斯譜半徑點(diǎn)數(shù)的上界和極圖。本文確定了時(shí),圍長為g的n階雙圈圖Aα-譜半徑的上界和極圖,推廣已有的成果。

1 記號(hào)與引理

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

設(shè)Cz、Ct是兩個(gè)頂點(diǎn)不相交的圈(z、t是正整數(shù),且z、t≥3,分別表示Cz、Ct的圈長。不失一般性,假定z≥t),v1是Cz的一個(gè)頂點(diǎn),vl是Ct的一個(gè)頂點(diǎn),B1(z,l,t)表示Cz、Ct通過長為l- 1(l≥1)的路v1v2…vl連接而成的圖(見圖1,當(dāng)l= 1 時(shí),圖1中的v1、vl將粘合成一點(diǎn))。設(shè)Pp+1、Pq+1、Pr+1是3個(gè)頂點(diǎn)不相交的路(p、q、r是正整數(shù),分別表示Pp+1、Pq+1、Pr+1的路長,且至多有一條路的長為1,因此假定r≥q≥p≥1),B2(p,q,r)表示將這3 條路的始點(diǎn)和終點(diǎn)粘合而得到的圖(圖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)的某些頂點(diǎn)接出一些樹形成的雙圈圖,分別稱為第一類雙圈圖和第二類雙圈圖,同時(shí)稱B1(z,l,t)、B2(p,q,r)為雙圈圖的基圖,并用B(n,g)表示所有圍長為g的n階雙圈圖所構(gòu)成的集合,B1(n,g)表示第一類型中圍長為g的n階雙圈圖所構(gòu)成的集合,B2(n,g)表示第二類型中圍長為g的n階雙圈圖所構(gòu)成的集合,B1*(z,l,t)表示在B1(z,l,t)的4 度頂點(diǎn)上接出一些懸掛邊所得的n階雙圈圖,B2*(p,q,r)表示在B2(p,q,r)的某個(gè)3 度頂點(diǎn)上接出一些懸掛邊所得的n階雙圈圖,B22*(p,q,r)表示在B2(p,q,r)的某個(gè)2 度頂點(diǎn)上接出一些懸掛邊所得的n階雙圈圖。

引理1[2-3]設(shè)α∈[0,1) ,G為連通圖,u、w是G的兩個(gè)頂點(diǎn),uvi∈E(G) 且wvi?E(G)(i=1,2,…,k,k≤n),X=(x1,x2,…,xn)T為對(duì)應(yīng)ρα(G)的Perron向量,G′為從G中刪除邊uvi并加上邊wvi得到的圖。若xw≥xu,則ρα(G) <ρα(G′)。

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

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

引理2[1]設(shè)G為n階圖,其最大度為Δ,若,則ρα(G) ≥αΔ+,當(dāng)且僅當(dāng)且G=Sn時(shí)等式成立。

引理3[1]設(shè)G是沒有孤立頂點(diǎn)的通圖,若α∈[0,1) ,則

引理4設(shè),n≥2g- 1,則

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

情形1:g= 3。

證明:g= 3 時(shí),根據(jù)n≥2g- 1,n取最小值5。

根據(jù)對(duì)稱性,不妨設(shè)x2≥x4,則

根據(jù)引理1,得到

情形2:g≥4。

證明:令h=n- 2g+ 1,根據(jù)引理3,可得

根據(jù)引理2,可得

由于n≥2g- 1,g≥4,不難驗(yàn)證

從而

2 主要結(jié)果

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

定理1設(shè)α∈[0,1) ,G∈B1(n,g),則ρα(G) ≤,當(dāng)且僅當(dāng)時(shí)等號(hào)成立。

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

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

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

現(xiàn)在證明G中在B1(g,1,g)上接出的樹都是星。假設(shè)在B1(g,1,g)的某個(gè)頂點(diǎn)vi處接出的樹Ti不是星,則Ti中存在非懸掛邊vivj;對(duì)邊vivj應(yīng)用推論1,可得G′∈B1(n,g)使得ρα(G) <ρα(G′),這與假設(shè)G為B1(n,g)中Aα-譜半徑最大的圖矛盾。因此,G中在B1(g,1,g)上接出樹都是星。

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

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

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

定理2設(shè)1,則,當(dāng)且僅當(dāng)時(shí)等號(hào)成立。

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

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

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

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

情形1:q-p≤1。

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

由引理2可得

再由引理3,可得

情形2:q-p≥2。

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

由引理2可得

再由引理3,可得

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

當(dāng)z取最大值時(shí),

從而

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

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

現(xiàn)在證明q-p≤1時(shí),

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

綜合以上討論z≥0。

由引理2可得

再由引理3,可得

當(dāng)z取最大值時(shí),

從而

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

定理3G是圍長為g的n階雙圈圖,設(shè),則

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

猜你喜歡
上界情形頂點(diǎn)
過非等腰銳角三角形頂點(diǎn)和垂心的圓的性質(zhì)及應(yīng)用(下)
避免房地產(chǎn)繼承糾紛的十二種情形
四種情形拖欠勞動(dòng)報(bào)酬構(gòu)成“拒不支付”犯罪
公民與法治(2020年4期)2020-05-30 12:31:34
一個(gè)三角形角平分線不等式的上界估計(jì)
關(guān)于頂點(diǎn)染色的一個(gè)猜想
一道經(jīng)典不等式的再加強(qiáng)
出借車輛,五種情形下須擔(dān)責(zé)
公民與法治(2016年9期)2016-05-17 04:12:18
Nekrasov矩陣‖A-1‖∞的上界估計(jì)
擬分裂情形下仿射Weyl群Cn的胞腔
正則微分系統(tǒng)帶權(quán)第二特征值的上界
清远市| 承德市| 平南县| 延长县| 忻城县| 蕲春县| 永吉县| 华蓥市| 舒兰市| 绿春县| 榆社县| 烟台市| 渭源县| 平陆县| 星子县| 冕宁县| 贵德县| 朔州市| 论坛| 康乐县| 民勤县| 香格里拉县| 琼中| 西昌市| 陆丰市| 彭州市| 嘉鱼县| 呼伦贝尔市| 衢州市| 松桃| 平乐县| 鹤岗市| 榆林市| 永新县| 礼泉县| 平潭县| 青海省| 东港市| 邵东县| 临武县| 瓮安县|