圈的一類運算圖的電阻距離和基爾霍夫指標

摘要： 將圈 Cn（n≥3）的每條邊替換為完全圖Kr（r≥2），得到的圖記作Kr（ Cn），利用電網絡理論中的串并聯原理、星網變換和割點性質，給出了Kr（ Cn）的電阻距離和基爾霍夫指標計算公式，所得結果推廣了已有研究中環狀硅酸鹽網絡的電阻距離和基爾霍夫指標的結論。

關鍵詞：電阻距離；基爾霍夫指標；星網變換

中圖分類號： O157.5

文獻標志碼： A

1 引言與預備知識

設G是一個連通圖，圖的距離函數是圖上的內在度量。圖上最廣為人知的距離函數是（最短路）距離，其中圖G的任意兩個頂點之間的距離定義為連接它們的最短路的長度。1993年，KLEIN和RANDIC' ［1］提出了電阻距離的概念。如果把圖G的每條邊都看作一個電阻（單位電阻），則G可以看作一個電網絡N。圖G中任意兩個頂點u和ν之間的電阻距離，記為Ω（u，ν），定義為這兩個節點之間的等效電阻，即單位電流從其中的一個節點流入，從另外一個節點流出時這兩點間所產生的電勢差。距離與電阻距離的不同之處在于，兩點間距離只與連接這兩點的最短路的長度有關，而兩點間電阻距離不僅與連接這兩點的最短路的長度有關，還與連接這兩點的路的數目有關。因此相比于距離，電阻距離更能反映圖的整體性質^［2］。

因為電阻距離更適合于用來描述化學分子中原子之間的波狀的相互作用，所以電阻距離在化學中有著重要的應用。特別地，基于電阻距離定義的化學分子拓撲指標，在QSAR（定量結構活性關系）和QSPR（定量結構性質關系）的研究中發揮了重要作用。圖的基爾霍夫指標就是基于電阻距離定義的一個重要的化學分子拓撲指標。圖G的基爾霍夫指標，記作Kf（G），定義為G中所有頂點對之間的電阻距離之和^［1］，即

Kf（G）=∑ult;νΩ（u，ν）。

近年來，通過對圖做一元運算或者二元運算，學者們給出了多類運算圖的電阻距離和基爾霍夫指標計算公式^［3-7］。特別地，由完全圖構造的圖類的電阻距離和基爾霍夫指標得到了關注和研究。利用電網絡理論中的消去原理等，李云翔等給出完全圖線性鏈的電阻距離以及基爾霍夫指標的計算公式^［8］，SARDAR等給出了鏈狀硅酸鹽網絡和環狀硅酸鹽網絡的電阻距離和基爾霍夫指標的計算公式^［9］。事實上，鏈狀硅酸鹽網絡可看作將一條n個點的路pn的每條邊用4個頂點的完全圖K4替換后所得到的圖，而環狀硅酸鹽網絡可看作將一個n個點的圈Cn的每條邊用4個頂點的完全圖K4替換后所得到的圖。受這些結果的啟發，本文考慮將圈Cn的每條邊用頂點數為r的完全圖Kr替換后所得到圖Kr（Cn）的電阻距離和基爾霍夫指標。

下面介紹要用到的電網絡中的一些原理和性質。首先介紹電阻的串并聯原理。

串聯原理 若頂點u和ν之間只有k個電阻值分別為r1，r2，… ，rk的電阻串聯在一起，則

Ω（u，ν）=r1+r2+… +rk。

并聯原理 若頂點u和ν之間只有k個電阻值分別為r1，r2，… ，rk的電阻并聯在一起，則

Ω（u，ν）=1r1+1r2+… +1rk^-1。

如果將連通圖G中的頂點k去掉后G-k不連通，則稱k為圖G割點。下面介紹電路理論中的割點性質。

割點性質 設k是連通圖G的一個割點，如果頂點u和ν屬于G-k的不同連通分支，則Ω（u，ν）=Ω（u，k）+Ω（k，ν）。

下面介紹星網變換。設Kr是一個包含r個頂點的完全圖且頂點集合V（Kr）={ν1，ν2，… ，νr}，其每條邊的電阻距離均為1，如圖1。設Sr是r+1個頂點的星圖，其每條邊的電阻距離都是1r，令Sr的頂點集合V（Sr）={ν1，ν2，… ，νr，t}，如圖2。

星網變換^［10］ 對任意一個電網絡N，Kr是它的一個子網絡，且每條邊的電阻值是1，則Kr可以被每條邊的電阻值均是1r的Sr替換，得到的新的電網絡N*是N的一個等價電網絡，即對N中的任意兩個點u和ν，有ΩN（u，ν）=ΩN*（u，ν）。

2 Kr（Cn）的電阻距離和基爾霍夫指標

設Kr（Cn）是將圈Cn中的每條邊用完全圖Kr代替后所得到的圖，即將Cn中的每條邊擴充成一個完全圖Kr，例如K4（C5），如圖3所示。

利用串并聯原理、星網變換和割點性質計算Kr（Cn）的電阻距離和基爾霍夫指標，用ΩK表示Kr（Cn）的電阻距離函數，du表示頂點u的度。

定理1 設Cn是頂點數為n的圈（n≥3），u和ν是Kr（Cn）中距離為d的兩個頂點，則

（1） 當du=dν=2r-2時，

ΩK（u，ν）=2d（n-d）rn。

（2）當du=r-1，dν=2r-2時，

ΩK（u，ν）=（2d-1）（2n-2d+1）2rn+1r。

（3）當du=dν=r-1時，

ΩK（u，ν）=2（d-1）（n-d+1）rn+2r。

證明 分別對Kr（Cn）的n個完全圖Kr進行星網變換，得到一個等價的電網絡K*r（Cn），即K*r（Cn）是由將Kr（Cn）中的n個完全圖Kr全部用星圖Sr替換得到，其中Sr的每條邊的電阻距離都是1r 。Kr（Cn）及其等價電網絡K*r（Cn）分別如圖4、5所示。用ΩK*表示K*r（Cn）的電阻距離函數。由于Kr（Cn）中任意兩點之間的電阻距離等于K*r（Cn）中所對應兩點之間的電阻距離，結合串并聯原理和割點性質，有

（1） 當du=dν=2r-2時，

ΩK（u，ν）=ΩK*（u，ν）=2dr·2n-2dr2dr+2n-2dr=2d（n-d）rn。

（2）" 當du=r-1，dν=2r-2時，

ΩK（u，ν）=ΩK*（u，ν）=1r +

［1r +2（d-1）1r ］［（2n-2d+1）1r ］［1r +2（d-1）1r ］+［（2n-2d+1）1r ］

=1r +（2d-1）（2n-2d+1）2rn。

（3） 當du=dν=r-1時，

ΩK（u，ν）=ΩK*（u，ν）=1r +

［1r +1r +2（d-2）1r ］［（2n-2d+2）1r ］［1r +1r +2（d-2）1r ］+［（2n-2d+2）1r ］+1r=2r+2（d-1）（n-d+1）rn。

證畢。

定理2 設Cn（n≥3）是頂點數為n的圈，則

Kf（Kr（Cn））=（r-1）2n3+6（r2-3r+2）n2-（r2+r-5）n6r。

證明 設V是圖Kr（Cn）的頂點集合，由基爾霍夫指標的定義，得

Kf（Kr（Cn））=

∑{u，ν}VΩK（u，ν）=

∑{u，ν}Vdu=dν=r-1ΩK（u，ν）+

∑{u，ν}Vdu=r-1，dν=2r-2ΩK（u，ν）+

∑{u，ν}Vdu=dν=2r-2ΩK（u，ν），（1）

下面分別計算等式（1）中等號右邊的三項。

首先計算第一項。當n為偶數時，對于d=1，有nC2r-2=n（r-2）（r-3）2個度為r-1的點對；對于2≤d≤n2，有nC1r-2C1r-2=n（r-2）2個距離為d的點對；對于d=n2+1，有n2C1r-2C1r-2=n（r-2）22個距離為n2+1的點對。由定理1，可得

∑{u，ν}Vdu=dν=r-1ΩK（u，ν）=2r·n（r-2）（r-3）2+n（r-2）2∑n2d=2［2（d-1）（n-d+1）rn+2r］+（2r+n2r）n（r-2）22=

n（r-2）（8r+nr-2n-20）4r+2（r-2）2r∑n2d=2［d（n-d+2）-1］。（2）

當n為奇數時，對于d=1，有nC2r-2=n（r-2）（r-3）2個度為r-1的點對；對于2≤d≤n+12，有nC1r-2C1r-2=n（r-2）2個距離為d的點對。同樣由定理1，可得

∑{u，ν}Vdu=dν=r-1ΩK（u，ν）=2r·n（r-2）（r-3）2+n（r-2）2∑n+12d=2［2（d-1）（n-d-1）rn+ 2r ］=

n（r-2）（r-3）r+2（r-2）2r∑n+12d=2［d（n-d+2）-1］。（3）

下面計算第二項。當n為偶數時，對于1≤d≤n2，有nC12r-4個距離為d的點對。結合定理1，有

∑{u，ν}Vdu=r-1，dν=2r-2ΩK（u，ν）=2n2（r-1）∑n2d=1［2（d-1）（2n-2d+1）2rn+ 1r ］=

（r-2）r∑n2d=1［d（4n-4d+4）-1］。（4）

當n為奇數時，對于1≤d≤n-12，有nC12r-4個距離為d的點對；對于d=n+12，有nC1r-2=n（r-2）個距離為n+12的點對。結合定理1，有

∑{u，ν}Vdu=r-1，dν=2r-2ΩK（u，ν）=n（r-2）（ 1r +n2r）+n（2r-4）∑n-12d=1［（2d-1）（2n-2d+1）2rn + 1r ］=

n（n+2）（r-2）2r+（r-2）r∑n-12d=1［d（4n-4d+4）-1］。（5）

再來計算第三項。當n為偶數時，對于1≤d≤n2-1，有n個距離為d的點對；對于d=n2，有n2個距離為n2的點對。由定理1可得

∑{u，ν}Vdu=dν=2r-2ΩK（u，ν）=n2r·n2+n∑n2-1d=12d（n-d）rn=n24r+ 2r ∑n2-1d=1d（n-d）。（6）

當n為奇數時，對于1≤d≤n-12，有n個距離為d的點對。結合定理1，有

∑{u，ν}Vdu=dν=2r-2ΩK（u，ν）=n∑n2-1d=12d（n-d）rn=2r∑n-12d=1d（n-d）。（7）

最后，計算Kf（Kr（Cn））。當n為偶數時，將等式（2）、（4）、（6）代入等式（1），

Kf（Kr（Cn））=（r2-4r+3）n2-4（r-2）n4r+

1r ∑n2d=1［2（r2-2r+1）dn-2（r2-2r+1）d2+4（r2-3r+2）d-2r2+7r-6］=

（r2-4r+3）n2-4（r-2）n4r+2（r2-2r+1）nr∑n2d=1d-2（r2-2r+1）nr∑n2d=1d2+

1r ∑n2d=1［4（r2-3r+2）d-2r2+7r-6］=

（r2-4r+3）n2-4（r-2）n4r+2（r2-2r+1）nr ·n（n+2）8-

2（r2-2r+1）r·n（n+1）（n+2）24+ 1r ·n（r-2）［n（r-1）+1］2=

（r-1）2n3+6（r2-3r+2）n2-（r2+r-5）n6r。

當n為奇數時，將等式（3）、（5）、（7）代入等式（1），

Kf（Kr（Cn））=（r-1）（r-2）n2+2（r-2）2n-r2+4r-42r+

1r∑n-12d=1［2（r2-2r+1）dn+2（-r2+2r-1）d2+4（r2-3r+2）d-2r2+7r-6］=

（r-1）（r-2）n2+2（r-2）2n-r2+4r-42r+2（r2-2r+1）nr∑n-12d=1d-

2（r2-2r+1）r∑n-12d=1d2+1r∑n-12d=1［4（r2-3r+2）d-2r2+7r-6］=

（r-1）（r-2）n2+2（r-2）2n-r2+4r-42r+2（r2-2r+1）nr·（n-1）（n+1）8-

2（r2-2r+1）r·n（n-1）（n+1）24+ 1r ·（n-1）（r-2）［n（r-1）-r+2］2=

（r-1）2n3+6（r2-3r+2）n2-（r2+r-5）n6r。

因此，

Kf（Kr（Cn））=（r-1）2n3+6（r2-3r+2）n2-（r2+r-5）n6r。

證畢。

注 當r=4時，K4（Cn）就是環狀硅酸鹽網絡。因此，本文所得結果推廣了SARDAR等^［9］的結果。

利用本文的結果可直接得到環狀硅酸鹽網絡的電阻距離和基爾霍夫指標。

推論1 設K4（Cn）（n≥3）是環狀硅酸鹽網絡，則

（1） 當du=dν=6時，

ΩK4（Cn）（u，ν）=d（n-d）2n。

（2） 當du=3，dν=6，時，

ΩK4（Cn）（u，ν）=（2d-1）（2n-2d+1）8n+14。

（3） 當du=dν=3時，

ΩK4（Cn）（u，ν）=（d-1）（n-d+1）2n+12。

推論2 設K4（Cn）（n≥3）是環狀硅酸鹽網絡，則

Kf（K4（Cn））=3n3+12n2-5n8。

參考文獻：

［1］ KLEIN D J， RANDIC' M. Resistance distance［J］. Journal of Mathematical Chemistry， 1993， 12（1）： 81-95.

［2］ 楊玉軍. 圖的電阻距離綜述［J］. 集美大學學報 （自然科學版）， 2022， 27（1）： 1-16.

［3］ YANG Y J. The Kirchhoff index of subdivisions of graphs［J］. Discrete Applied Mathematics， 2014， 171： 153-157.

［4］ YANG Y J， KLEIN D J. Resistance distance-based graph invariants of subdivisions and triangulations of graphs［J］. Discrete Applied Mathematics， 2015， 181： 260-274.

［5］ BU C J， YAN B， ZHOU X Q， et al. Resistance distance in subdivision-vertex join and subdivision-edge join of graphs［J］. Linear Algebra and its Applications， 2014， 458： 454-462.

［6］ LIU X G， ZHOU J， BU C J. Resistance distance and Kirchhoff index of R-vertex join and R-edge join of two graphs［J］. Discrete Applied Mathematics， 2015， 187： 130-139.

［7］ 劉群. 剖分點—邊冠圖的電阻距離和Kirchhoff 指標（英文）［J］. 數學進展， 2016， 45（2）： 176-184.

［8］ 李云翔， 徐思奧， 潘向峰. 完全圖線性鏈的電阻距離［J］. 合肥學院學報 （綜合版）， 2021， 38（5）： 5-13.

［9］ SARDAR M S， PAN X F， XU S A. Computation of resistance distance and Kirchhoff index of the two classes of silicate networks［J］. Applied Mathematics and Computation， 2020， 381： 125283.

［10］ ROSEN A. A new network theorem［J］. Journal of the Institution of Electrical Engineers， 1924， 62（335）： 916-918.

Resistance Distances and Kirchhoff Index of A Type of Graph Operation on Cycles

JIANG Yaxin， YANG Yujun

（School of Mathematics and Informational Sciences， Yantai University， Yantai 264005， China）

Abstract："Let Kr（Cn） be the graph obtained from the cycle Cn（n≥ 3） by replacing each edge of Cn with a complete graph Kr（n≥ 2）. In this paper， by applying the series and parallel principles， the star-mesh transformation and cut-vertex property， the expressions are given for resistance distances and Kirchhoff index of Kr（Cn），generalizing the previous works by Sardar et al.

Keywords："resistance distance; Kirchhoff index; star-mesh transformation

（責任編輯 李春梅）