三类乘积图的peripheral Wiener指标

董哈微

（闽江学院数学与数据科学学院，福建福州350001）

对于一个图G,图的点集和边集分别记为V(G)和E(G).图G的两个顶点u,v之间的距离指的是在图G中顶点u和顶点v之间的最短路的长度，记作dG(u,v)（不会产生混淆的话，简记为d(u,v)）.对v ∈V(G)，顶点v 的离心率ε(v)= max{d(u,v),u ∈V(G)}. 图G 的直径为最大离心率，即d(G)=max{ε(v) |v ∈V(G}.peripheral 顶点集P(G)指图G 中满足ε(v)=d(G)的所有顶点. 用 ||P(G) 表示图G 中peripheral 顶点的个数.

乘积图在许多领域，如人类遗传学、动态选址问题、网络问题等都扮演着重要角色[10].计算乘积图的拓扑指标也成为许多学者的研究课题.其中，第一个对这个课题进行研究的是Graovac 和Pisansk[11]，他们计算的是乘积图的Wiener 指标.稍后，Yeh 等[12]计算了在笛卡尔乘积、cluster 运算、连接运算、组合运算、corona乘积运算下的乘积图的Wiener指标.Sagan等[13]引入连接、笛卡尔乘积、Disjunction、对称差、张量积这6 种图运算，并计算出对应的乘积图的Wiener 多项式的公式.在文献[14]中，Kahsay A 和Narayankar K已经给出一些经典的乘积图的peripheral Wiener指标的计算公式.本文继续探讨这个问题，给出corona乘积、disjunction和对称差这3种运算的乘积图的peripheral Wiener指标的计算公式.

'

1主要结论

1.1 corona乘积图的公式

corona 乘积是一个常用的图运算[12].设G1和G2为两个图，拷贝 ||V(G1) 个G2，连接G1中的第i 个顶点和G2的第i 个拷贝中的每个顶点，其中i = 1,2,…, ||V(G1) ，得到的图为图G1和图G2的corona 乘积图，记为G1∘G2.

1.2 Disjuction乘积图的公式

1.3 对称差乘积图的公式

图G1和图G2的对称差乘积图[16]，记为G1⊕G2. 其是一个图，满足顶点集为V(G1)×V(G2)，并且点(v1,v2)和(u1,u2)相邻当且仅当u1v1∈E(G1)或u2v2∈E(G2)，但两者并不同时成立.定理3 设G1，G2是简单连通图，则

证明 计算可得，G1⊕G2有 ||V(G1)2||E(G2) + ||V(G2)2||E(G1)-2 ||E(G1) ||E(G2) 条边.任取点(u1,u2),(v1,v2)∈V(G1⊕G2).

情况1：u1v1∈E(G1)且u2v2∉E(G2)或者u1v1∉E(G1)且u2v2∈E(G2).

由G1⊕G2的定义，得d((u1,u2),(v1,v2))= 1.

情况2：u1v1∈E(G1)且u2v2∈E(G2).

由G1⊕G2的 定 义，那 么d((u1,u2),(v1,v2))＞1 且(u1,u2)(u1,v2)(v1,v2) 是 长 度 为2 的 路. 因 此d((u1,u2),(v1,v2))= 2.

情况3：u1v1∉E(G1)且u2v2∉E(G2).

若NG1(u1)⋂NG1(v1)≠ϕ，任取w1∈NG1(u1)⋂NG1(v1). 因为u1w1∈E(G1)，所以(u1,u2)(w1,u2)是G1⊕G2的 一 条 边. 因 为v1w1∈E(G1) 且u2v2∉E(G2)，所 以(w1,u2)(v1,v2) 是G1⊕G2的 一 条 边. 于 是(u1,u2)(w1,u2)(v1,v2)是G1⊕G2的长度为2的路.因此d((u1,u2),(v1,v2))= 2.

若NG1(u2)⋂NG1(v2)≠ϕ，与以上证明类似可知，d((u1,u2),(v1,v2))= 2.

若NG1(u1)⋂NG1(v1)= ϕ 且NG1(u2)⋂NG1(v2)= ϕ，任取w1∈NG1(u1)，w2∈NG1(v2). 因为u1w1∈E(G1)且u2w2∉E(G2)，所 以(u1,u2)(w1,w2) 是G1⊕G2的 一 条 边. 因 为w1v1∉E(G1) 且w2v2∈E(G2)，所 以(w1,w2)(v1,v2) 是G1⊕G2的 一 条 边. 于 是(u1,u2)(w1,w2)(v1,v2) 是G1⊕G2的 长 度 为2 的 路. 因 此d((u1,u2),(v1,v2))= 2.

由于G1，G2是连通图，根据情况2知，peripheral顶点集是G1⊕G2的所有顶点.任一顶点都是G1或G2中边的端点.

2 例子

在这部分，分别应用定理1、定理2和定理3，给出特殊图类的peripheral Wiener指标.

例1 设图G有n个顶点，m条边.图P2∘G被称为G的瓶颈图.如果P2是两个顶点的路，那么PW(P2∘G)= 5n2- 2n - 2m.

例2 如果Pm和Pn分别是m个和n个顶点的路，那么

例3 如果Km和Kn分别是m个和n个顶点的完全图，那么