王雪婷,王 燕,袁 凱

(煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,山東 煙臺(tái) 264005)

1 引言與預(yù)備知識(shí)

假定G為連通圖,頂點(diǎn)集為V(E)={v1,v2,…,vn},邊集合為E(G)。一般來講,圖G中任意兩個(gè)頂點(diǎn)之間的距離定義為連接它們的最短路徑的長度。1993年,KLEIN和RANDIC基于電網(wǎng)絡(luò)理論提出了新的距離函數(shù)[1]:圖中任意兩個(gè)頂點(diǎn)vi和vj之間的電阻距離定義為將G中每條邊用單位電阻替代后得到的電網(wǎng)絡(luò)中這兩個(gè)節(jié)點(diǎn)之間的凈有效電阻,記作ΩG(vi,vj)。新定義的電阻距離是電路圖上的距離函數(shù),相較于圖中的最短路徑,電阻距離更適合描述分子中的流體或波狀通信,同時(shí)也被廣泛應(yīng)用于物理、化學(xué)等學(xué)科領(lǐng)域。

近些年來,圖的基爾霍夫指標(biāo)的計(jì)算得到了極大的發(fā)展。一些特殊圖,如圈、完全圖、連通圖、循環(huán)圖、凱萊圖等的基爾霍夫指標(biāo)已經(jīng)有明確的計(jì)算公式[4-9]。 KLEIN等學(xué)者計(jì)算了一些在圖上做一元或者二元運(yùn)算所得到的圖,如三角化、三角剖分、合成圖[10-13]等的基爾霍夫指標(biāo),且所得的基爾霍夫指標(biāo)是由原圖的一些參數(shù)來表示,在一定程度上大大簡化了這些圖的基爾霍夫指標(biāo)的計(jì)算過程。

對(duì)于連通圖G,S(G)是將G中的每條邊用P2(長度為2的路)代替。更進(jìn)一步,在S(G)中,對(duì)原圖G中的每個(gè)頂點(diǎn)添加兩個(gè)懸掛點(diǎn),并使這兩個(gè)懸掛點(diǎn)相鄰,所得到的新圖記作RS(G)，見圖1。

2010年,CHEN[14]得到了連通圖S(G)中頂點(diǎn)對(duì)之間的電阻距離。 本文將在此基礎(chǔ)上給出計(jì)算RS(G)的基爾霍夫指標(biāo)的顯性公式。

圖1 圖G與其所對(duì)應(yīng)的RS(G)

2 RS(G)的電阻距離與基爾霍夫指標(biāo)

本節(jié)將計(jì)算RS(G)的電阻距離、基爾霍夫指標(biāo)、度乘以及度和基爾霍夫指標(biāo)。 為了方便區(qū)分,分為兩大部分進(jìn)行計(jì)算。首先介紹計(jì)算中用到的已知結(jié)果。Ω、ΩS和ΩR分別表示G、S(G)和RS(G)中的電阻距離。

引理1 設(shè)vk是連通圖G的一個(gè)割點(diǎn),若頂點(diǎn)vi和vj屬于G-vk的不同連通分支,則有ΩG(vi,vj)=ΩG(vi,vk)+ΩG(vk,vj)。

引理3[14]設(shè)G為連通圖,NS(vkl)表示頂點(diǎn)vkl∈V1在圖S(G)中的鄰點(diǎn)集合,則S(G)中任意兩頂點(diǎn)間的電阻距離為:

1)若vi,vj∈V(G),則有ΩS(vi,vj)=2Ω(vi,vj)。

3)若vkl,vpq∈V1,NS(vkl)={vk,vl},NS(vpq)={vq,vp},則有

2.1 RS(G)的電阻距離與基爾霍夫指標(biāo)

基于引理3,可以得到RS(G)中任意兩個(gè)頂點(diǎn)之間的電阻距離,結(jié)果如下。

定理1G為連通圖,則RS(G)中任意兩個(gè)頂點(diǎn)間的電阻距離為:

1)若vi,vj∈V(G),則有

ΩR(vi,vj)=2Ω(vi,vj)。

(1)

2)若vkl∈V1,NS(vkl)={vk,vl},vj∈V(G),則有

(2)

3)若vkl,vpq∈V1,NS(vkl)={vk,vl},NS(vpq)={vq,vp},則有

(3)

(4)

(5)

(6)

綜上所述,定理1得證。

根據(jù)定理1和基爾霍夫指標(biāo)的定義,可以計(jì)算得出RS(G)的基爾霍夫指標(biāo)的顯性公式。

定理2 假定G為具有n≥2個(gè)頂點(diǎn)、m條邊的連通圖,則

(7)

證明根據(jù)基爾霍夫指標(biāo)的定義以及V(RS(G))=V(S(G))∪V2有

(8)

根據(jù)文獻(xiàn)[11]的已知結(jié)果有

(9)

故有

(10)

因?yàn)閂(S(G))=V(G)∪V1, 所以對(duì)于等式(8)中的第三個(gè)求和可以分為兩個(gè)部分來計(jì)算：

(11)

首先計(jì)算

(12)

其次

(13)

由引理2,

(14)

若令Ω(vi)表示G中所有頂點(diǎn)與vi之間的電阻距離之和,則等式(13)中第二部分求和公式可變形計(jì)算為

(15)

故將式(14)、(15)代入式(13),再將式(12)、(13)代回式(11),最后將式(9)、(10)、(11)代入式(8)得

2.2 RS(G)的度和基爾霍夫指標(biāo)與度乘基爾霍夫指標(biāo)

定理3 假定G為具有n≥2個(gè)頂點(diǎn)、m條邊的連通圖,則

Kf+(RS(G))=72Kf(G)+18Kf+(G)+4Kf*(G)+10n2+3m2+11mn+m-2n。

證明由度和基爾霍夫指標(biāo)的定義以及V(RS(G))=V(S(G))∪V2有

(16)

現(xiàn)將等式(16)的右邊記為A1+A2+A3來進(jìn)行運(yùn)算。

首先計(jì)算A1,通過V(S(G))=V(G)∪V1可得

(17)

根據(jù)引理3,顯然有

這片子是以卡扎菲為原型的，但有時(shí)候我覺得這同樣也是以現(xiàn)在新一代小孩子為原型的嘛！觀察一下周圍的小孩子們，一個(gè)比一個(gè)大爺。孩子們最愛用的詞就是“我”?！拔摇笔撬麄兊倪壿嬈瘘c(diǎn)，也是終極目標(biāo)。我的利益我的情緒至高無上。

(18)

(19)

對(duì)于等式(17)右邊的后面三部分,則可直接引用文獻(xiàn)[10]、[11]的結(jié)果：

(20)

(21)

(22)

將等式(18)—(22)代入等式(17)中就可以得到

8Kf(G)+4Kf*(G)+6Kf+(G)+3m2-2n2-mn+m+2n。

(23)

其次計(jì)算A2,根據(jù)等式(10)顯然

(24)

(25)

根據(jù)定理1,先計(jì)算等式(25)右邊的第一部分

(26)

而式(25)右邊的第二和第三部分已經(jīng)由式(12)、(13)得出,故代入式(25)可得

(27)

于是將式(23)、(24)和(27)代回式(16)就能得到

Kf+(RS(G))=8Kf(G)+4Kf*(G)+6Kf+(G)+3m2-2n2-mn+m+2n+

72Kf(G)+18Kf+(G)+4Kf*(G)+10n2+3m2+11mn+m-2n。

定理4 假定G為具有n≥2個(gè)頂點(diǎn)、m條邊的連通圖,則

證明由度乘基爾霍夫指標(biāo)的定義以及V(RS(G))=V(S(G))∪V2有

(28)

將等式(28)的右邊三部分記為B1+B2+B3。

根據(jù)V(S(G))=V(G)∪V1先求B1：

(29)

其中

2Kf*(G)+4Kf+(G)+8Kf(G)，

(30)

下面對(duì)等式(29)中的第三部分求和,根據(jù)等式(21)、(22)有

2Kf*(G)+2Kf+(G)+m2-n2+m+n。

(31)

最后求等式(28)右邊的B3:

在定理2和定理3的證明過程中,B3化簡結(jié)果中的三部分已經(jīng)求得結(jié)果,分別見等式(26)、(12)、(13)。

最后將求得的B1、B2、B3的結(jié)果代入等式(28)即可得到定理4:

Kf*(RS(G))=2Kf*(G)+4Kf+(G)+8Kf(G)+2[Kf*(G)+m(m-n)]+