正則圖的Q-圖的(度)基爾霍夫指標

李佳建

(蘭州交通大學 數理學院， 甘肅 蘭州 730070)

本文只考慮簡單無向圖，設G=(V(G),E(G))是n個頂點、m條邊的連通圖。圖G的頂點i與頂點j之間的電阻距離[1]，是指以單位電阻代替G中每條邊后構造出的電網絡中節點i與j之間的等效電阻，記為Ωij。

圖的電阻距離與通常的距離相似，是在圖上定義的一種新的距離函數。因此，與基于距離的圖不變量類似，定義了基于電阻距離的各種圖不變量，其中，最著名的是基爾霍夫指標，也稱為總有效電阻，用R(G)來表示，定義為所有頂點對之間的電阻距離之和[2-4]，即

近年來，研究人員對這一指標給予了較多的關注，將其拓展引入了兩種新的指標，其中一個是乘法度-基爾霍夫指標[5]：

另一個是加法度-基爾霍夫指標[6]：

這里ri表示圖G中頂點i的度。

圖G的線圖，記作l(G)，是指以圖G的邊集為頂點集，l(G)的兩個頂點相鄰當且僅當對應的G的兩條邊在G中相鄰。圖G的Q-圖，記作Q(G)，是指在圖G的每條邊中插入一個新頂點，然后把鄰接的邊對應的新插入頂點相連接而得到的圖，圖1給出了圖G，l(G)、Q(G)的示例。

文獻[7]研究了剖分圖的基爾霍夫指標，文獻[8]給出了Q-圖的電阻距離，文獻[9]給出了正則圖的線圖的電阻距離，文獻[10]得到了剖分圖、三角剖分圖的基爾霍夫指標以及加法度-基爾霍夫指標和乘法度-基爾霍夫指標，文獻[11-12]分別刻畫了G與l(G)和G與Q(G)它們的基爾霍夫指標之間的關系。此外，還有一些關于其它圖的度-基爾霍夫指標的相關結果[13-15]。

受上述文獻的啟發，這里主要討論正則圖G的Q(G)圖的(乘法度或加法度)基爾霍夫指標與l(G)的基爾霍夫指標之間的關系。

(a) G (b) l(G) (c) Q(G)圖1 圖G及其Q(G)

1 預備知識

引理1.1[8]設圖G是一個有n個頂點、m條邊的r-正則圖，則

(3)當i,j∈V(i≠j)且Г(i)={e1,e2,…,er}，Г(j)={f1,f2,…,fr}時，有

引理1.2[16]設圖G為n階連通圖，那么所有相鄰頂點間的電阻距離之和為n-1，即

2 主要結果

定理2.1 設圖G為具有n(n≥2)個頂點、m條邊的r-正則連通圖，則

證明由基爾霍夫指標定義，有

(1)

首先，由引理1.1(1)知

(2)

其次，由引理1.1(2)知

(3)

(4)

(5)

由引理1.2知

(m-1)(n-1)/[r(r+1)],

(6)

因此，由式(4)、(5)、(6)可得

(7)

結合式(1)、(2)、(3)、(7)，定理得證。證畢。

下面給出Q(G)的加法度或乘法度-基爾霍夫指標與l(G)的基爾霍夫指標之間的關系。

定理2.2 設圖G為n≥2個頂點、m條邊，r-正則的連通圖，則

證明由加法度-基爾霍夫指標的定義，有

下面計算等式右邊的3個部分。

(1)對于第一部分，由引理2.1知

由式(2)知

綜上所述,定理2.2得證。

定理2.3 設圖G為n≥2個頂點，m條邊，r-正則的連通圖，則

證明由乘法度-基爾霍夫指標的定義，有

證畢。