點面圖的基爾霍夫指標(biāo)

王大勇,楊玉軍

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

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

(1)

后來, 人們進一步將頂點的度考慮進來, 定義了2種修正的基爾霍夫型指標(biāo). 一種是度和基爾霍夫指標(biāo)[2], 記作Kf+(G), 定義為

(2)

其中di表示G中頂點i的度.另一種是度乘積基爾霍夫指標(biāo)[3], 定義為

(3)

基爾霍夫指標(biāo)不僅是圖上的一個重要的不變量, 而且在化學(xué)上還是一個重要的分子結(jié)構(gòu)描述符,在QSAR(定量結(jié)構(gòu)活性關(guān)系)和QSPR(定量結(jié)構(gòu)性質(zhì)關(guān)系)中有著重要的應(yīng)用. 因此, 圖的基爾霍夫指標(biāo)得到了廣泛的研究. 基爾霍夫指標(biāo)的研究主要集中于基爾霍夫指標(biāo)的計算. 一方面, 對于一些特殊圖類, 人們給出了這些圖的基爾霍夫指標(biāo)的精確的顯式表達式. 另一方面, 對于一些通過在圖上做一元或者二元運算得到的圖, 如剖分圖、三角化圖以及合成圖等[4-8], 人們給出了這些圖的由原圖中的參數(shù)表示的基爾霍夫指標(biāo)計算公式, 從而使得這些圖的基爾霍夫指標(biāo)的計算得到了極大的簡化. 在本文中, 我們將給出嵌入在定向曲面上的三角化圖G的點面圖K(G)的基爾霍夫指標(biāo)的計算公式. 首先給出點面圖的定義.

定義1 設(shè)圖G是嵌入在定向表面Σ上的三角化圖(即每個面都是三角形),頂點集合為V(G)={v1,v2,…,vn},邊集合為E(G)={e1,e2,…,em}和面集合為F(G)={φ1,φ2,…,φf}.圖G的點面圖K(G)定義為

V(K(G))=V(G)∪F(G)

且K(G)的邊集合為

V(φ),φ∈F(G)}.

由點面圖的定義可以看出, 圖G的點面圖K(G)可以通過下面的方式得到: 在圖G的每個面中插入一個新的頂點, 然后再將新的頂點與所在面的3個頂點連邊. 例如, 頂點數(shù)為4的完全圖K4在平面上的嵌入就是一個三角化圖, 該圖的點面圖K(K4)如圖1所示.

圖1 完全圖K4及其點面圖K(K4)Fig.1 The complete graph K4 and its vertex-face graph K(K4)

在本文中, 我們將給出嵌入在可定向曲面上的三角化圖G的點面圖K(G)的基爾霍夫指標(biāo)計算公式. 所得結(jié)果表明,K(G)的基爾霍夫指標(biāo)可以由圖G的頂點數(shù)、面數(shù)、頂點的度、基爾霍夫指標(biāo)等參數(shù)表示.

2 點面圖的基爾霍夫指標(biāo)

本節(jié)將給出點面圖的基爾霍夫指標(biāo)計算公式. 在給出主要結(jié)果之前, 首先介紹電網(wǎng)絡(luò)中的一個重要結(jié)果——Foster公式.

引理1[9]設(shè)圖G是頂點數(shù)為n的連通圖,則有

(4)

其中i～j表示頂點i和頂點j相鄰,且和號取遍所有相鄰的點對.

應(yīng)用電網(wǎng)絡(luò)理論中的星形-三角形變換和電阻距離的局部和法則, SHANGGUAN和CHEN得到了點面圖的電阻距離計算公式[10],見引理2.

引理2[10]設(shè)G是嵌在定向表面Σ的三角化圖,頂點集合和面集合分別為V(G)={v1,v2,…，vn}和F(G)={φ1,φ2,…，φf},那么圖G點面的K(G)的頂點集合為V(K(G))=V(G)∪F(G)中頂點間的電阻距離為

(1) 如果vi,vj∈V(G),那么

(5)

(2) 如果vi∈V(G),φj∈F(G),V(φj)={a,b,c},那么

(6)

其中rφj(G)=rab(G)+rac(G)+rbc(G);

(3) 如果φi,φj∈F(G),V(φi)={d,e,f},V(φj)={a,b,c},那么

(7)

現(xiàn)在給出本節(jié)的主要結(jié)果.

定理1 設(shè)G是嵌入在定向曲面Σ的頂點數(shù)為n且面數(shù)為f的三角化圖, 則

(8)

證明由基爾霍夫指標(biāo)的定義以及V(K(G))=V(G)∪F(G), 可知

(9)

下面分別計算等式(9)中等號右邊的3項.

(i)首先計算等式(9)等號右邊的第一項. 由引理2, 當(dāng)vi,vj∈V(G)時,

因而,

(10)

(ii)再計算等式(9)等號右邊的第二項.由引理2可知,當(dāng)vi∈V(G),φj∈F(G)(V(φj)={a,b,c})時,

其中rφj(G)=rab(G)+rac(G)+rbc(G).因此

(11)

一方面,?vj∈V(G),vj同時屬于G的dj個不同的面,因此

(12)

(13)

將式(12)和(13)代入式(11), 可得

(14)

(iii) 最后, 計算等式(9)右邊的第三項.由引理2, 對φi,φj∈F(G),

rij(K(G))=

因此,

(15)

顯然,

rkl(G)中出現(xiàn)了didj-2次, 因此由Foster公式可得

Kf*(G)-2(n-1) .

(16)

另一方面, 同樣由Foster公式可得

(17)

將等式(16)和(17)代入等式(15), 可得

(18)

綜合以上結(jié)果, 將等式(10),(14)和(18)代入等式(9), 通過簡單運算就可得到定理中的結(jié)果.