王大勇,楊玉軍

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

1 引言與預備知識

(1)

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

(2)

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

(3)

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

定義1 設圖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個頂點連邊. 例如, 頂點數為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)的基爾霍夫指標計算公式. 所得結果表明,K(G)的基爾霍夫指標可以由圖G的頂點數、面數、頂點的度、基爾霍夫指標等參數表示.

2 點面圖的基爾霍夫指標

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

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

(4)

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

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

引理2[10]設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)

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

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

(8)

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

(9)

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

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

因而,

(10)

(ii)再計算等式(9)等號右邊的第二項.由引理2可知,當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)中出現了didj-2次, 因此由Foster公式可得

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

(16)

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

(17)

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

(18)

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