三類乘積圖的peripheral Wiener指標(biāo)

董哈微

（閩江學(xué)院數(shù)學(xué)與數(shù)據(jù)科學(xué)學(xué)院，福建福州350001）

對于一個圖G,圖的點(diǎn)集和邊集分別記為V(G)和E(G).圖G的兩個頂點(diǎn)u,v之間的距離指的是在圖G中頂點(diǎn)u和頂點(diǎn)v之間的最短路的長度，記作dG(u,v)（不會產(chǎn)生混淆的話，簡記為d(u,v)）.對v ∈V(G)，頂點(diǎn)v 的離心率ε(v)= max{d(u,v),u ∈V(G)}. 圖G 的直徑為最大離心率，即d(G)=max{ε(v) |v ∈V(G}.peripheral 頂點(diǎn)集P(G)指圖G 中滿足ε(v)=d(G)的所有頂點(diǎn). 用 ||P(G) 表示圖G 中peripheral 頂點(diǎn)的個數(shù).

乘積圖在許多領(lǐng)域，如人類遺傳學(xué)、動態(tài)選址問題、網(wǎng)絡(luò)問題等都扮演著重要角色[10].計算乘積圖的拓?fù)渲笜?biāo)也成為許多學(xué)者的研究課題.其中，第一個對這個課題進(jìn)行研究的是Graovac 和Pisansk[11]，他們計算的是乘積圖的Wiener 指標(biāo).稍后，Yeh 等[12]計算了在笛卡爾乘積、cluster 運(yùn)算、連接運(yùn)算、組合運(yùn)算、corona乘積運(yùn)算下的乘積圖的Wiener指標(biāo).Sagan等[13]引入連接、笛卡爾乘積、Disjunction、對稱差、張量積這6 種圖運(yùn)算，并計算出對應(yīng)的乘積圖的Wiener 多項式的公式.在文獻(xiàn)[14]中，Kahsay A 和Narayankar K已經(jīng)給出一些經(jīng)典的乘積圖的peripheral Wiener指標(biāo)的計算公式.本文繼續(xù)探討這個問題，給出corona乘積、disjunction和對稱差這3種運(yùn)算的乘積圖的peripheral Wiener指標(biāo)的計算公式.

'

1主要結(jié)論

1.1 corona乘積圖的公式

corona 乘積是一個常用的圖運(yùn)算[12].設(shè)G1和G2為兩個圖，拷貝 ||V(G1) 個G2，連接G1中的第i 個頂點(diǎn)和G2的第i 個拷貝中的每個頂點(diǎn)，其中i = 1,2,…, ||V(G1) ，得到的圖為圖G1和圖G2的corona 乘積圖，記為G1°G2.

1.2 Disjuction乘積圖的公式

1.3 對稱差乘積圖的公式

圖G1和圖G2的對稱差乘積圖[16]，記為G1⊕G2. 其是一個圖，滿足頂點(diǎn)集為V(G1)×V(G2)，并且點(diǎn)(v1,v2)和(u1,u2)相鄰當(dāng)且僅當(dāng)u1v1∈E(G1)或u2v2∈E(G2)，但兩者并不同時成立.定理3 設(shè)G1，G2是簡單連通圖，則

證明 計算可得，G1⊕G2有 ||V(G1)2||E(G2) + ||V(G2)2||E(G1)-2 ||E(G1) ||E(G2) 條邊.任取點(diǎn)(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是連通圖，根據(jù)情況2知，peripheral頂點(diǎn)集是G1⊕G2的所有頂點(diǎn).任一頂點(diǎn)都是G1或G2中邊的端點(diǎn).

2 例子

在這部分，分別應(yīng)用定理1、定理2和定理3，給出特殊圖類的peripheral Wiener指標(biāo).

例1 設(shè)圖G有n個頂點(diǎn)，m條邊.圖P2°G被稱為G的瓶頸圖.如果P2是兩個頂點(diǎn)的路，那么PW(P2°G)= 5n2- 2n - 2m.

例2 如果Pm和Pn分別是m個和n個頂點(diǎn)的路，那么

例3 如果Km和Kn分別是m個和n個頂點(diǎn)的完全圖，那么