單圈圖的Sombor指標

胡文潔，高珊，楊星光

(1.湖北大學數(shù)學與統(tǒng)計學學院，湖北 武漢 430062；2.湖北大學計算機與信息工程學院，湖北 武漢 430062；3.應用數(shù)學湖北省重點實驗室(湖北大學)，湖北 武漢 430062)

0 引言

設圖G=(V,E)是一個簡單無向連通圖.圖G的點數(shù)|G|稱為G的階.G的邊數(shù)記為‖G‖.對圖G中任意的點v,用NG(v)表示點v在圖G中的所有鄰點的集合.點v在圖G中的度dG(v)(簡記為d(v))指G中與v關聯(lián)的邊的條數(shù), 即dG(v)=|NG(v)|.如果d(v)=maxvi∈Vd(vi),那么稱v是圖G中的最大度點. 圖G的度為1的點稱為G的懸掛點, 與懸掛點關聯(lián)的邊稱為G的懸掛邊.我們用G-x或G-xy分別表示刪去x∈V(G)或xy∈E(G)后得到的圖.同樣地,G+xy表示在G的不相鄰兩點x,y之間添加一條邊后得到的圖.

令G和H是兩個簡單連通圖,且u∈V(G),v∈V(H).把u和v粘合在一起得到的圖記為GuvH,或簡記為GuH.

滿足‖G‖=|G|-1的連通圖稱為樹.滿足‖G‖=|G|的連通圖稱為單圈圖. 記Un是所有n階單圈圖的集合.記Cn,Pn,Sn分別為n階圈,n階路和n階星.Sn的最大度點稱為Sn的中心.

圖G的Sombor指標定義為

圖G的Sombor指標是由Gutman I.[2]基于圖G的邊的端點的度提出的一種新的拓撲指標.Sombor指標自提出以來,受到廣大學者的關注,得到許多新的研究成果[1-5].2021年,Cruz-Rada[1]得到了單圈圖和雙圈圖的Sombor指標的極值,Gutman I.[2]給出了Sombor指標的一些性質(zhì),分別刻畫了連通圖的Somber指標的極值和極圖.最近,Wang-Zhang[3]刻畫了給定直徑的樹的Sombor指標的極值和極圖.Zhou-Lin-Miao[4-5]分別給出了給定匹配數(shù)和最大度的單圈圖的Sombor指標的極值，并刻畫了對應的極圖.

本文中,我們進一步研究單圈圖的Sombor指標,得到了n階單圈圖第二大和第二小時的Sombor指標的值,并刻畫了Sombor指標達到第二大和第二小時的極圖.

1 相關引理

本節(jié)中,我們給出幾個在主要結論證明中需要用到的引理.

引理1.1[2]令G是一個圖,且u∈V(G),v是星圖Sr的中心,w是Sr的懸掛點,則

SO(GuwSr)

引理1.2設G是一個圖,如果xy?E(G),yz∈E(G).令G*=G-yz+xy.如果dG(x)≥dG(z),那么SO(G)

引理1.2的證明由r>0,y2>(y-r)2,可得

因此g(r)(x,y)是關于x≥1的遞增函數(shù),也是關于y≥1的遞增函數(shù).

設G是一個圖,我們定義x?Gz當且僅當dG(x)≥dG(z),dG(x′)≤dG(z′)，對任意x′∈NG(x){z}和z′∈NG(z){x}.

引理1.3設G是一個圖,u,v∈V(G).令Gp,r(p≥1,r≥1)是圖G兩個點u,v處分別粘上p,r條懸掛邊后得到的圖, 則或者SO(Gp,r)

引理1.3的證明設u′,v′是Gp,r的兩個懸掛點,且uu′∈E(Gp,r),vv′∈E(Gp,r),則Gp+1,r-1?Gp,r-vv′+uv′,且Gp-1,r+1?Gp,r-uu′+vu′.如果dGp,r(u)≥dGp,r(v),則由引理1.2可知SO(Gp,r)

2 主要結論

Cruz-Rada[1]分別刻畫了n階單圈圖的Sombor指標達到最大和最小時的極圖,并給出了下面的結果.

定理2.1[1]如果G∈Un, 那么

SO(Cn)≤SO(G)≤SO(Un,3).

下面我們進一步考慮n階單圈圖的Sombor指標.注意到U3={C3},U4={C4,U4,3}.由定理2.1可知,SO(C4)

對任意的圖G∈Un,令Cg=v1v2vgv1是G中唯一圈.令Ti為G-E(Cg)的包含vi(1≤i≤g)的分支.則Ti是一棵以vi為根點的樹,其中1≤i≤g.如果|Ti|>1, 稱Ti是非平凡的.

定理2.2設G∈Un{Cn}.則

SO(G)≥φ(n)

(1)

而且不等式中等式成立當且僅當G∈Ln.

SO(G)≥φ(n),

且等式成立時僅有G∈Ln.

先給出下面記號:

E′=∪i+j≥5Eij,

Eij={uv∈E(G):dG(u)=i,dG(v)=j}.

記nij=|Eij|,n′=|E′|，則n=n12+n13+n22+n′, 且

(2)

且不等式中等式成立時僅有E′=E23.

因為GCn,故g≤n-1,且Cg中至少存在一個度為3的點. 于是|E′∩E(Cg)|≥2.接下來證明下面命題.

命題1n′≥n12+2,進而n′≥3或n13≥1.

命題1的證明因為g≤n-1,故G-E(Cg)存在非平凡分支Ti.如果E12=?,那么viw∈E′或viw∈E13,其中w是vi在Ti中的鄰點,即n′≥3或n13≥1.因此不妨假設E12≠?.令φ為E12到E′E(Cg)的映射.對任意的uv∈E12,dG(v)=2,dG(u)=1.不妨假設uv∈E(Tl)(1≤l≤g),則Tl中存在唯一(v,vl)-路P.設vl在P上的鄰點為w,則vlw∈E′E(Cg).若Tl中存在度≥3的點,在Tl中唯一的(v,vl)-路P上選取離v最近的3度點設為x,P上到v距離比d(x,v)小1的點記作y,即φ是單射.從而|E′E(Cg)|≥|E12|,即n′≥n12+2≥3.

我們考慮如下兩種情形:

情形1：n12≥1.

在此情形下,由命題1可知n′≥n12+2.由(2)式可得

=φ(n).

上式等式成立時,n12=1,n′=n12,n13=0，且不等式(2)中等式成立, 因此G∈Ln.

情形2：n12=0.

在此情形下,由命題1可知n′≥3或n′=2,n13≥1.由(2)式可知

=φ(n).

綜合情形1和情形2的證明,我們完成了定理2.2的證明.

定理2.3令G∈Un{Un,3}.則

SO(G)≤ψ(n)

(3)

=ψ(n).

將SO(G)看作關于g的函數(shù)

由函數(shù)的單調(diào)性和引理1.4可得函數(shù)關于g單調(diào)遞減.則

<ψ(n).

因此下面不妨假設g≤n-1且當g≥4時,GUn,g.

先證明如下命題.

命題2g=3.

命題2的證明如果g≥4, 則GUn,g.設dG(v1)=max{dG(vi):1≤i≤g},因為g≤n-1,故dG(v1)≥3.令G′=G-v2v3+v1v3,則G′∈Un{Un,3}.注意到dG(v1)≥dG(v2).因此由引理2.2,SO(G′)>SO(G),與G的取法矛盾. 于是g=3.

接下來考慮如下兩種情形.

情形1：G-E(Cg)中存在唯一的非平凡分支.

=ψ(n).

情形2：G-E(Cg)至少包含兩個非平凡分支.