圖運算下的基爾霍夫指數

邢抱花，孫旻昊

（安慶師范大學數理學院，安徽安慶 246133）

設G=(V(G),E(G))是無向的連通圖，|V(G)|和|E(G)|分別表示G的頂點數和邊數，d G(v)表示圖G中頂點v的度，G-w表示在圖G中刪去頂點w以及與w關聯的邊后得到的圖。若圖G-w不再連通，則稱頂點w是圖G的割點，圖G的不含割點的極大連通子圖稱為G的塊，圖G的兩頂點u、v的距離d G(u,v)是指圖G中連接u、v的最短路長度。將圖G的每條邊用單位電阻代替后，得到對應的電網絡，圖G中任意兩點u和v的電阻距離ΩG(u,v)是對應電網絡中的有效電阻。[1]電阻距離不同于一般的距離僅僅代表著兩個頂點之間的最短路長度，它更能刻畫整個圖各頂點的關系，更適合描述分子中的流體和波狀通信。自1993年，Klein和Randic首次提出電阻距離概念之后，關于它的相關結論被陸續發表，其中一部分研究內容是有關基于電阻距離的拓撲不變量，最常見的是基爾霍夫指數[2]，是1994年Bonchev和Balaban等人提出的，被定義為圖G中所有無序頂點對的電阻距離總和。即

2007年和2012年，陳海燕等人和Gutman等人又分別定義了度積基爾霍夫指數[3]與度和基爾霍夫指數[4]

關于它們的部分結論可參看文獻[2-18]及其參考文獻。

近年來，有關基爾霍夫指數計算的結論主要分兩方面：一方面是某些特殊圖自身的基爾霍夫指數計算，如正則圖[5]、硅酸鹽網絡[6]、脂環烴衍生物網絡[7]等；另一方面是經過圖運算后的圖的基爾霍夫指數計算，如在文獻[8]和[9]中，楊玉軍等人計算了剖分圖S(G)、疊代剖分圖Sk(G)、三角剖分圖T(G)和疊代三角剖分圖Tk(G)的基爾霍夫指數；在文獻[10]中，于越等人定義了兩類圖運算，并計算對應圖RT(G)和H(G)的基爾霍夫指數；……