李佳建

(蘭州交通大學(xué) 數(shù)理學(xué)院， 甘肅 蘭州 730070)

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

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

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

另一個(gè)是加法度-基爾霍夫指標(biāo)[6]：

這里ri表示圖G中頂點(diǎn)i的度。

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

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

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

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

1 預(yù)備知識(shí)

引理1.1[8]設(shè)圖G是一個(gè)有n個(gè)頂點(diǎn)、m條邊的r-正則圖，則

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

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

2 主要結(jié)果

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

證明由基爾霍夫指標(biāo)定義，有

(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)

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

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

定理2.2 設(shè)圖G為n≥2個(gè)頂點(diǎn)、m條邊，r-正則的連通圖，則

證明由加法度-基爾霍夫指標(biāo)的定義，有

下面計(jì)算等式右邊的3個(gè)部分。

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

由式(2)知

綜上所述,定理2.2得證。

定理2.3 設(shè)圖G為n≥2個(gè)頂點(diǎn)，m條邊，r-正則的連通圖，則

證明由乘法度-基爾霍夫指標(biāo)的定義，有

證畢。