加權Szeged指標的上下界

胡 姣， 劉蒙蒙

(蘭州交通大學 數理學院， 甘肅 蘭州 730070)

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

對于邊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個頂點，則nu(e)+nv(e)+n0(e)=n。

Wiener指標是最早研究也是研究最廣的拓撲指標，Wiener在1947年[2]提出了Wiener指標W(G)的概念，即

2014年，Nagarajan等[8]首次給出了加權Szeged指標的定義：

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

本文首先給出了加權Szeged指標的上界，并刻畫了達到上界的極值圖。其次，根據加權Szeged指標與其他拓撲指標、直徑之間的關系，得到了不同條件下加權Szeged指標的下界，并刻畫了相應的極值圖。

1 上 界

給出加權Szeged指標的上界，證明Bok等人提出的加權Szeged指標最大的圖是完全平衡二部圖的猜想。

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

其中：∣N(u)∩N(v)∣表示與頂點u與v公共鄰點的個數。

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

等號成立當且僅當圖G為完全平衡二部圖。

證明：n=2時，結論顯然成立。

(1)

因此，

2 下 界

首先用邊(a,b)-Zagreb指標，第一Zagreb指標和加權頂點PI指標給出加權Szeged指標的下界并刻畫相應的極值圖。其次，用邊數m和直徑d給出加權Szeged指標的下界并刻畫相應的極值圖。

=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的直徑為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個頂點和m條邊的連通圖，則

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

等號成立當且僅當對任意的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)，有

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

定理4 令G是具有n個頂點的二部圖，則

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

等號成立當且僅當G?Sn。

證明：因為G是二部圖，所以對于任意的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)

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

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

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

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

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

3 結 語

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