亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        關(guān)于圖的距離無符號(hào)拉普拉斯譜半徑的下界

        2021-06-10 05:28:44朱銀芬王國平
        關(guān)鍵詞:連通分支主子拉普拉斯

        朱銀芬,王國平,陳 星

        (1.新疆工程學(xué)院數(shù)理學(xué)院,烏魯木齊 830029;2.新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,烏魯木齊830017)

        如果一個(gè)連通圖G的點(diǎn)集是V(G)={v1,v2,…,vn},那么圖G的距離矩陣D(G)=(dij),其中dij表示點(diǎn)vi與vj之間的距離.令TrG(vi)表示點(diǎn)vi到圖G中其它所有點(diǎn)的距離之和,Tr(G)表示對(duì)角線位置的元素是TrG(vi)的對(duì)角矩陣.

        圖G的距離拉普拉斯矩陣及距離無符號(hào)拉普拉斯矩陣分別被表示為L(zhǎng)D(G)=Tr(G)-D(G)與QD(G)=Tr(G)+D(G),它們的最大特征值λL(G)和λQ(G)分別是圖G的距離拉普拉斯譜半徑與距離無符號(hào)拉普拉斯譜半徑.

        Aouchiche和Hansen在文獻(xiàn)[1]中引入了圖的距離拉普拉斯譜與距離無符號(hào)拉普拉斯譜的概念,并且在文獻(xiàn)[2]中證明了樹中星圖具有最小距離拉普拉斯譜半徑.近年來,關(guān)于距離拉普拉斯譜與距離無符號(hào)拉普拉斯譜的研究已經(jīng)有了長(zhǎng)足的進(jìn)展.Xing與Zhou[3]確定了雙圈圖中具有最小距離譜半徑與最小距離無符號(hào)拉普拉斯譜半徑的唯一圖.文獻(xiàn)[4]確定了在樹、單圈圖、雙圈圖、給定懸掛點(diǎn)數(shù)與連通度的圖中具有最小距離無符號(hào)拉普拉斯譜半徑的圖.Liu與Lu[5]確定了給定團(tuán)數(shù)的距離無符號(hào)拉普拉斯譜半徑的界.Lin和Zhou[6]刻畫了在給定懸掛點(diǎn)數(shù)與邊連通度的圖中具最小的距離拉普拉斯譜半徑的唯一圖的特性.牛愛紅等[7]確定了給定匹配數(shù)或給定連通度的二部圖中具有最小距離拉普拉斯譜半徑的極圖.

        本文確定了給定匹配數(shù)的圖的距離無符號(hào)拉普拉斯譜半徑的下界.

        1 引理

        先給出一些已知的結(jié)果.

        引理1[1]圖G是連通圖,若uv?E(G),那么λQ(G+uv)<λQ(G).

        引理2[1]設(shè)圖G是n階連通圖,那么λQ(G)≥λQ(Kn)=2(n-1).

        引理4[8]設(shè)A1與A2是n階實(shí)對(duì)稱矩,那么

        λn(A2)+λi(A1)≤λi(A1+A2),

        其中λi(A)是A的第i大特征值.

        引理5[8]設(shè)A是n階實(shí)對(duì)稱矩陣,M是A的s(s

        λi+n-s(A)≤λi(M)≤λi(A)(1≤i≤s),

        其中λi(A)是A的第i大特征值.

        若有X?V(G),那么圖G的子圖G-X是將圖G的X中的點(diǎn)與X點(diǎn)相關(guān)聯(lián)的邊同時(shí)刪除后得到的.圖G的一個(gè)匹配是圖G中不相鄰的邊的集合,那么所有匹配中含有最大的邊數(shù)叫做圖G的匹配數(shù).若圖G的某個(gè)連通分支的點(diǎn)數(shù)是奇數(shù),那么稱這個(gè)連通分支是圖G的奇連通分支;否則,稱這個(gè)連通分支是偶連通分支.

        引理6[9-10]如果圖G是匹配數(shù)為m的n階圖,那么

        n-2m=max{o(G-X)-|X|:X?V(G)},

        其中o(G-X)是圖G-X的奇連通分支數(shù).

        引理7[11]如果圖G是連通圖,那么λQ(G)>λL(G).

        2 定理及推論

        ?

        Kn,則由引理1知λQ(G)>λQ(Kn).

        設(shè)G-X0的所有連通分支為H1,H2,…,Hk,Hk+1,…,Ht,其中H1,H2,…,Hk是G-X0的奇連通分支,Hk+1,…,Ht是G-X0的偶連通分支.

        這樣,λQ(G)>2n-m.

        下面假定s

        情況1t=k.

        在這種情況下G-X0的所有連通分支H1,H2,…,Hk都為奇連通分支.設(shè)|V(Hi)|=ni,則ni是奇數(shù)(i=1,2,…,k).

        下面先就G?Ks∨(Kn1∪Kn2∪…∪Knk)的情況進(jìn)行驗(yàn)證.

        為方便書寫,不妨假定n1≤n2≤…≤nk.若n1=…=nk=1,則n=k+s.

        注意到n-2m=k-s,這樣就有s=m,這與s

        令M={v1u1,v2u2,…,vsus}∪Mp∪Mp+1∪…∪Mk,則M就是G的一個(gè)匹配.這樣,

        注意到當(dāng)p≤i≤k時(shí),ni≥np.因此,

        若p≥3,則n1=n2=1.設(shè)u與v分別是Kn1與Kn2中的那個(gè)點(diǎn).在QD(G)中取2×2階主子矩陣:

        因?yàn)閗≥3,所以m≥s+1,進(jìn)而

        TrG(v)=TrG(u)=

        s+2(n-s-1)≥2n-m-1,

        由引理4與引理5,得到

        λQ(G)≥λQ(A)≥λQ(A′)=2n-m+1>2n-m.

        若p=2,那么n1=1,而對(duì)于所有的2≤i≤k都有ni≥3.設(shè)u∈Kn1且v∈Ks,類似可得,在QD(G)中取2×2階主子矩陣:

        因?yàn)閗≥3,于是得到m≥s+2.進(jìn)而

        TrG(v)=s+2(n-s-1)≥2n-m,

        TrG(u)=n-1.

        由引理4與引理5,得到

        λQ(G)≥λQ(B)≥λQ(B′)=

        2n-m.

        若p=1,則對(duì)于所有的1≤i≤k都有ni≥3.下面針對(duì)k≥3的取值情況分類討論.

        若k≥4,設(shè)u和v是Kn1中不同的兩個(gè)點(diǎn).在QD(G)中取2×2階主子矩陣:

        TrG(v)=TrG(u)=
        s+n1-1+2(n-s-n1)≥2n-m.

        由引理4與引理5得

        λQ(G)≥λQ(C)≥λQ(C′)=

        2n-m+1>2n-m.

        當(dāng)k=3且n3=3時(shí),設(shè)u∈Kn1,v∈Kn2.在QD(G)中取2×2階主子矩陣:

        TrG(v)=TrG(u)=s+n1-1+2(n-s-n1)
        ≥2n-s-4≥2n-m-1.

        由引理4與引理5,得

        λQ(G)≥λQ(D)≥λQ(D′)=

        2n-m+1>2n-m.

        當(dāng)k=3且n3≥5時(shí),設(shè)u和v是Kn1中不同的兩個(gè)點(diǎn).在QD(G)中取2×2階主子矩陣:

        進(jìn)而有

        TrG(v)=TrG(u)=

        s+n1-1+2(n-s-n1)≥2n-m.

        由引理4與引理5,得

        λQ(G)≥λQ(E)≥λQ(E′)=2n-m+1>2n-m.

        綜上所述,當(dāng)G?Ks∨(Kn1∪Kn2∪…∪Knk)時(shí),λQ(G)>2n-m.當(dāng)GKs∨(Kn1∪Kn2∪…∪Knk)時(shí),由引理1可知,

        λQ(G)>λQ(Ks∨(Kn1∪Kn2∪…∪Knk)),

        進(jìn)而有λQ(G)>2n-m.

        情況2t>k.

        此時(shí),G-X0不僅有k個(gè)奇連通分支,且有t-k個(gè)偶連通分支.將圖G的每一個(gè)偶連通分支Hj(k+1≤j≤t)中的某個(gè)點(diǎn),與奇連通分支H1中的某個(gè)點(diǎn)連接一條邊后得到的圖記作G′.

        顯然G′-X0也有k個(gè)奇連通分支,且圖G′的最大匹配數(shù)m(G′)≥m.由引理6,有

        n-2m≥n-2m(G′)≥o(G′-X0)-|X0|=

        o(G-X0)-|X0|=n-2m.

        猜你喜歡
        連通分支主子拉普拉斯
        偏序集的序連通關(guān)系及其序連通分支
        “貓主子”的日常
        獻(xiàn)給貓主子的秋の珍味
        類星圖的2種度結(jié)合重構(gòu)數(shù)*1
        基于超拉普拉斯分布的磁化率重建算法
        一個(gè)圖論問題的簡(jiǎn)單證明
        新課程(下)(2015年9期)2015-04-12 09:23:30
        交換環(huán)的素譜與極大譜的連通性
        位移性在拉普拉斯變換中的應(yīng)用
        關(guān)于連通分支的兩道習(xí)題
        含有一個(gè)參數(shù)的p-拉普拉斯方程正解的存在性
        西川结衣中文字幕在线| 中文字幕久热精品视频免费| 亚洲欧美另类日本久久影院| 久久久免费精品国产色夜| 中文字日产幕码三区的做法大全| 国产午夜精品一区二区三区| 久久精品片| 乱色欧美激惰| 国产精品无码av一区二区三区 | 国产99页| 手机在线中文字幕av| 国产毛片黄片一区二区三区| 久久99久久99精品中文字幕| 无码AV高潮喷水无码专区线| 国产成人高清精品亚洲一区| 中文字幕一区二区三区的| 亚洲春色在线视频| 亚洲一区综合精品狠狠爱| 久久精品国产亚洲av调教| 蜜桃一区二区三区视频网址| 亚洲av无码国产精品色软件下戴| 久久久久亚洲女同一区二区| 午夜亚洲精品视频网站| 一本久久a久久免费综合| 久久不见久久见免费影院www| 四虎影视久久久免费| 最好的99精品色视频大全在线| 日本真人添下面视频免费| 亚洲av无码不卡久久| 亚洲乱码少妇中文字幕| 精品国产亚洲av高清日韩专区| 性感女教师在线免费观看| 在线成人一区二区| 亚洲毛片αv无线播放一区| 69久久精品亚洲一区二区| 日韩内射美女片在线观看网站| 亚洲av无码一区二区三区系列| 无码伊人久久大蕉中文无码| 日韩一区二区三区精品视频| 免费人成网ww555kkk在线| 在线视频一区二区日韩国产 |