加權(quán)Szeged指標(biāo)的上下界

胡 姣， 劉蒙蒙

(蘭州交通大學(xué) 數(shù)理學(xué)院， 甘肅 蘭州 730070)

本文所有圖形都是無向的、有限的、簡單的。術(shù)語和符號來自參考文獻(xiàn)[1]。 如果G是一個(gè)圖，那么V(G)是G的頂點(diǎn)集，E(G)是G的邊集。對于頂點(diǎn)u,v∈V(G)，dG(u)表示圖G中頂點(diǎn)u的度，即與u相鄰的點(diǎn)的數(shù)目；dG(u,v)表示圖G中的頂點(diǎn)u和頂點(diǎn)v之間的距離，即連接頂點(diǎn)u和頂點(diǎn)v之間最短路徑的長度。N(u)表示與頂點(diǎn)u相鄰的所有頂點(diǎn)的集合。diam(G)表示圖G的直徑，即圖G中任意2個(gè)頂點(diǎn)之間的最大距離。

對于邊uv=e∈E(G)，定義以下集合:

Nu(e)={x∈V(G)|dG(u,x)

Nv(e)={x∈V(G)|dG(v,x)

N0(e)={x∈V(G)|dG(u,x)=dG(v,x)}。

令nu(e)=|Nu(e)|，nv(e)=|Nv(e)|，n0(e)=|N0(e)|。若圖G有n個(gè)頂點(diǎn)，則nu(e)+nv(e)+n0(e)=n。

Wiener指標(biāo)是最早研究也是研究最廣的拓?fù)渲笜?biāo)，Wiener在1947年[2]提出了Wiener指標(biāo)W(G)的概念，即

2014年，Nagarajan等[8]首次給出了加權(quán)Szeged指標(biāo)的定義：

同時(shí)計(jì)算了廣義層次積圖的加權(quán)Szeged指標(biāo)。 Pattabiraman和Kandan在文獻(xiàn)[6]中計(jì)算了笛卡爾積圖和冠圖的加權(quán)Szeged指標(biāo)。Atanasov等[9]證明了在具有最小加權(quán)Szeged指標(biāo)的樹中，最大度不超過16。Bok等[10]確定了在所有的樹圖中， 星圖的加權(quán)Szeged指標(biāo)最大， 證明了在所有二部圖中具有最大加權(quán)Szeged指標(biāo)的是完全平衡二部圖， 給出了具有最小加權(quán)Szeged指標(biāo)的樹的一些性質(zhì)，同時(shí)提出了2個(gè)猜想。即在所有連通圖中，加權(quán)Szeged指標(biāo)最大的圖是完全平衡二部圖，加權(quán)Szeged指標(biāo)最小的圖是樹圖。

本文首先給出了加權(quán)Szeged指標(biāo)的上界，并刻畫了達(dá)到上界的極值圖。其次，根據(jù)加權(quán)Szeged指標(biāo)與其他拓?fù)渲笜?biāo)、直徑之間的關(guān)系，得到了不同條件下加權(quán)Szeged指標(biāo)的下界，并刻畫了相應(yīng)的極值圖。

1 上 界

給出加權(quán)Szeged指標(biāo)的上界，證明Bok等人提出的加權(quán)Szeged指標(biāo)最大的圖是完全平衡二部圖的猜想。

引理2[11]令G是具有n個(gè)頂點(diǎn)，t(G)個(gè)三角形的連通圖，則

其中：∣N(u)∩N(v)∣表示與頂點(diǎn)u與v公共鄰點(diǎn)的個(gè)數(shù)。

定理1 令G是具有n(n≥2)個(gè)頂點(diǎn)，m條邊，t(G)個(gè)三角形的連通圖，則

等號成立當(dāng)且僅當(dāng)圖G為完全平衡二部圖。

證明：n=2時(shí)，結(jié)論顯然成立。

(1)

因此，

2 下 界

首先用邊(a,b)-Zagreb指標(biāo)，第一Zagreb指標(biāo)和加權(quán)頂點(diǎn)PI指標(biāo)給出加權(quán)Szeged指標(biāo)的下界并刻畫相應(yīng)的極值圖。其次，用邊數(shù)m和直徑d給出加權(quán)Szeged指標(biāo)的下界并刻畫相應(yīng)的極值圖。

=3×1×(n-1)+4×2×(n-2)+4×3×(n-3)+…+4×(n-2)×2+

3(n-1)×1

定理2 令G是具有n(n≥3)個(gè)頂點(diǎn)且不包含三角形的連通圖， 則

等號成立當(dāng)且僅當(dāng)圖G的直徑為2。

證明:對于任意的e=uv∈E(G)，由于G不包含三角形，故nu(e)≥dG(u),nv(e)≥dG(v)，因此nu(e)nv(e)≥dG(u)dG(v)，從而，對所有的邊e=uv∈E(G)，有

定理3 令G是具有n個(gè)頂點(diǎn)和m條邊的連通圖，則

wSz(G)≥PIw(G)-M1(G)

等號成立當(dāng)且僅當(dāng)對任意的e=uv∈E(G)有nu(e)=1或nv(e)=1。

證明：對于任意的e=uv∈E(G)，由不等式(nu(e)-1)(nv(e)-1)≥0，可得nu(e)+nv(e)≤nu(e)nv(e)+1。 因此，對所有的邊e=uv∈E(G)，有

等號成立當(dāng)且僅當(dāng)對任意的e=uv∈E(G)有nu(e)=1或nv(e)=1，即證。

定理4 令G是具有n個(gè)頂點(diǎn)的二部圖，則

wSz(G)≥(n-1)M1(G),

等號成立當(dāng)且僅當(dāng)G?Sn。

證明：因?yàn)镚是二部圖，所以對于任意的e=uv∈E(G)，都有nu(e)+nv(e)=n，由不等式(nu(e)-1)(nv(e)-1)≥0，可得nu(e)nv(e)≥nu(e)+nv(e)-1=n-1。因此，對所有的邊e=uv∈E(G)，有

=(n-1)M1(G)

當(dāng)且僅當(dāng)對任意的邊e=uv∈E(G)，nu(e)=1或nv(e)=1時(shí)等號成立。由于GKn，則diam(G)≥2。當(dāng)diam(G)>2時(shí)，則一定存在一條最短路P4=v0v1v2v3，對于邊e=v1v2，有nv1(e)=nv2(e)≥2，矛盾，因此diam(G)=2。對任意的邊e=uv∈E(G)，不妨設(shè)nu(e)=1，則離u近的只有u本身。 對于任意的w∈V(G)，要么與u和v等距，要么均為v的鄰點(diǎn)，否則diam(G)≠2。因?yàn)镚是二部圖，故所有的w均為v的懸掛點(diǎn)，因此G?Sn，即證。

定理5 令G具有m條邊，直徑為d(d≥2)的圖，則

等號成立當(dāng)且僅當(dāng)圖G?Pd+1(d≥2)。

證明：對任意的e=uv∈E(G)，有nu(e)·nv(e)≥1且dG(u)+dG(v)≥3。由于圖G的直徑為d，則路Pd+1包含在G中。 因此，有

等號成立當(dāng)且僅當(dāng)對所有的e=uv∈E(G)E(Pd+1)都有nu(e)=nv(e)=1且dG(u)+dG(v)=3；當(dāng)d≥2時(shí)，上式不能同時(shí)成立，因此圖G不包含Pd+1以外的邊，即G?Pd+1。

3 結(jié) 語

本文給出了加權(quán)Szeged指標(biāo)的上界，證明了Bok等人提出的加權(quán)Szeged指標(biāo)最大的圖是完全平衡二部圖的猜想。用邊(a,b)-Zagreb指標(biāo)、第一Zagreb指標(biāo)和加權(quán)頂點(diǎn)PI指標(biāo)給出了加權(quán)Szeged指標(biāo)的下界并刻畫了相應(yīng)的極值圖，用邊數(shù)m和直徑d給出了加權(quán)Szeged 指標(biāo)的下界并刻畫了相應(yīng)的極值圖。