加权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 指标的下界并刻画了相应的极值图。