圖的電阻距離和基爾霍夫指標(biāo)綜述

葛春雨，劉家保

(1.蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州 730070；2.安徽建筑大學(xué) 數(shù)理學(xué)院，安徽 合肥 230601)

0 引言

設(shè)圖G=(V(G)，E(G))為n(n≥2)個頂點(diǎn)m條邊的連通圖， 頂點(diǎn)度序列Δ=d1≥d2≥…≥dn=δ>0， 其中di=dvi.圖G的拉普拉斯矩陣L(G)=D(G)-A(G)， 其特征值μ1≥μ2≥…≥μn-1>μn=0， 其中D(G)和A(G)分別是圖G的對角矩陣和鄰接矩陣． 若圖G中每個頂點(diǎn)的度相等， 則稱G是正則圖；若圖G中所有頂點(diǎn)的度均為r， 則稱G為r-正則圖， 記作Γr.

基爾霍夫指標(biāo)， 記作Kf(G)， 也被稱為全有效電阻[2]或有效圖電阻[3]． 它定義為圖G中所有頂點(diǎn)對的電阻距離之和， 即

圖的基爾霍夫指標(biāo)是一個與圖的拉普拉斯特征值密切相關(guān)的圖的拓?fù)洳蛔兞浚?1996年， Gutman等[4]和Klein等[5]證明了連通圖G的基爾霍夫指標(biāo)也可以表示為：

其中μ1≥μ2≥…≥μn-1>μn=0為圖G的拉普拉斯矩陣的特征值.

近幾十年來， 對更多圖形的電阻距離和基爾霍夫指標(biāo)的研究越來越多， 如距離正則圖、 Fullerene圖、 樹圖、 加權(quán)圖、 輪圖和扇形圖、 Cayley圖等． 特別地， 楊玉軍和Klein[6]在2013年給出了電阻距離的遞推公式以及該公式的應(yīng)用.

隨著研究的深入， 結(jié)合頂點(diǎn)的度， 又進(jìn)一步衍生出度-基爾霍夫指標(biāo)． 2007年， 陳海燕和張?；鵞7]定義了乘法度-基爾霍夫指標(biāo)：

其中di(dj)表示第i(j)個頂點(diǎn)的度.

2012年， Gutman等[8]定義了加法度-基爾霍夫指標(biāo)：

2011年， 文獻(xiàn)[9]定義了圖G的超-基爾霍夫指標(biāo)：

圖G的線圖記作l(G)， 是指以圖G的邊集為頂點(diǎn)集，l(G)的兩個頂點(diǎn)相鄰當(dāng)且僅當(dāng)對應(yīng)的G的兩條邊在G中相鄰． 圖G的三角剖分記作T(G)， 是將G的每條邊uv變換成一個三角形uwv， 其中w是與uv相關(guān)聯(lián)的新頂點(diǎn).

下面給出圖的一些運(yùn)算的定義.

定義1設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則S(G)，Q(G)，R(G)，t(G)定義分別如下:

1)剖分圖S(G)是將圖G的每條邊替換為一條長度為2的路所構(gòu)成的圖；

2)Q-圖Q(G)是通過在圖G的每條邊上引入一個新的頂點(diǎn)， 然后通過G將相鄰邊上的新頂點(diǎn)對應(yīng)連接起來而形成的圖；

3)R-圖R(G)是通過在圖G的每條邊上放置一個與之相關(guān)的新頂點(diǎn)， 然后將每個新頂點(diǎn)連接到相應(yīng)邊的末端頂點(diǎn)來構(gòu)造的圖；

4)全圖t(G)是頂點(diǎn)對應(yīng)于圖G的頂點(diǎn)集和邊集并集， 且t(G)的兩個頂點(diǎn)相鄰， 當(dāng)且僅當(dāng)對應(yīng)的元素在G中相鄰或關(guān)聯(lián).

定義2設(shè)G1和G2是兩個圖且V(G1)={u1，u2， …，u|V(G1)|}，V(G2)={v1，v2， …，v|V(G2)|}， 則

1)圖G1和G2的聯(lián)圖G1+G2：

V(G1+G2)=V(G1)∪V(G2);

E(G1+G2)=E(G1)∪E(G2)∪{(u1，u2)|u1∈V(G1)，u2∈V(G2)}.

2)圖G1和G2的冠圖G1°G2：取一個G1的拷貝和|V(G1)|個G2的拷貝， 然后將G1的第i個頂點(diǎn)和第i個G2的拷貝的所有頂點(diǎn)都相連，i=1， 2， …，|V(G1)|.

1 一些運(yùn)算圖的電阻距離和基爾霍夫指標(biāo)

圖運(yùn)算已經(jīng)被廣泛地應(yīng)用于分析從現(xiàn)實(shí)世界中抽象出來的具有拓?fù)湫再|(zhì)的復(fù)雜網(wǎng)絡(luò)． 其中字典積、 笛卡爾積、 聯(lián)圖、 冠圖和星圖等， 這些運(yùn)算圖的其他拓?fù)渲笜?biāo)已有結(jié)果， 這里給出一些運(yùn)算圖的電阻距離和基爾霍夫指數(shù).

2012年， 高興等[10]給出了正則圖的線圖l(G)、 剖分圖S(G)和全圖t(G)的基爾霍夫指標(biāo)的公式并刻畫了下界成立的極圖.

定理1.1[10]設(shè)G是一個連通的d-正則圖， 具有n(n≥2)個頂點(diǎn)， 則

推論1.1[10]設(shè)G是一個連通的d-正則圖， 具有n(n≥2)個頂點(diǎn)， 則

等式成立當(dāng)且僅當(dāng)G=Kn.

定理1.2[10]設(shè)G是一個連通的d-正則圖， 具有n(n≥2)個頂點(diǎn)， 則

推論1.2[10]設(shè)G是一個連通的d-正則圖， 具有n(n≥2)個頂點(diǎn)， 則

等式成立當(dāng)且僅當(dāng)G=Kn.

定理1.3[10]設(shè)G是一個連通的d-正則圖， 具有n(n≥2)個頂點(diǎn)， 則

推論1.3[10]設(shè)G是一個連通的d-正則圖， 具有n(n≥2)個頂點(diǎn)， 則

等式成立當(dāng)且僅當(dāng)G=Kn.

2013年， You等[11]修正了高興等[10]在2012年求出的正則圖的全圖的基爾霍夫公式及其下界．

定理1.4[11]設(shè)G是一個連通的d-正則圖， 具有n(n≥2)個頂點(diǎn)， 則

推論1.4[11]設(shè)G是一個連通的d-正則圖， 具有n(n≥2)個頂點(diǎn)， 則

2013年， 王維忠等[12]刻畫了正則圖的Q(R)-圖的基爾霍夫指標(biāo)的公式和下界.

定理1.5[12]設(shè)G是一個n階的連通r-正則圖(r≠2)， 則

推論1.5[12]設(shè)G是一個n階的連通r-正則圖(r≠2)， 則

定理1.6[12]設(shè)G是一個n階的連通r-正則圖， 則

推論1.6[12]設(shè)G是一個n階的連通r-正則圖， 則

2014年， 楊玉軍[13]計算了正則分子圖的一些xyz變換的Kirchhoff指標(biāo)， 其在文獻(xiàn)[14]中證明了一般圖的剖分圖S(G)的基爾霍夫指標(biāo)可以用圖G的基爾霍夫指標(biāo)、 乘法度-基爾霍夫指標(biāo)、 加法度-基爾霍夫指標(biāo)、 頂點(diǎn)數(shù)n、 邊數(shù)m表示． 這個結(jié)果推廣了高興等[10]關(guān)于正則圖的剖分圖S(G)的基爾霍夫指標(biāo)的結(jié)果．

2015年， Sun等[15]給出了一般圖的剖分圖的電阻距離和基爾霍夫指標(biāo)的另一種計算公式.

定理1.7[13]設(shè)圖G為n個頂點(diǎn)和m條邊的r-正則圖(r≥2)， 則

定理1.8[13]設(shè)圖G為n個頂點(diǎn)和m條邊的r-正則圖(r≥2)， 則

定理1.9[13]設(shè)圖G為n個頂點(diǎn)和m條邊的r-正則圖(r≥2)， 則

定理1.10[13]設(shè)圖G為n個頂點(diǎn)和m條邊的r-正則圖(r≥2)， 則

定理1.11[13]設(shè)圖G為n個頂點(diǎn)和m條邊的r-正則圖(r≥2)， 則

定理1.12[14]設(shè)G是一個連通圖， 具有n(n≥2)個頂點(diǎn)和m條邊， 則

2015年， 楊玉軍和Klein[16]得到了剖分和三角剖分圖的加法度(乘法度)-基爾霍夫指標(biāo)公式， 以及一個新的三角剖分基爾霍夫指標(biāo)公式， 并給出了圖的迭代剖分和三角剖分的(加法度-、 乘法度-)基爾霍夫指標(biāo)公式.

定理1.13[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則剖分圖S(G)的加法度-基爾霍夫指標(biāo)為:

Kf+(S(G))=4Kf+(G)+4Kf*(G)+(m+n)(m-n+1)+2m(m-n).

定理1.14[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則剖分圖S(G)的乘法度-基爾霍夫指標(biāo)為:

Kf*(S(G))=8Kf*(G)+2m(2m-2n+1).

定理1.15[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則迭代剖分圖Sk(G)的乘法度-基爾霍夫指標(biāo)為:

定理1.16[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則迭代剖分圖Sk(G)的加法度-基爾霍夫指標(biāo)為:

定理1.17[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則迭代剖分圖Sk(G)的基爾霍夫指標(biāo)為:

(m-n+1).

定理1.18[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則三角剖分圖T(G)的基爾霍夫指標(biāo)為:

定理1.19[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則三角剖分圖T(G)的加法度-基爾霍夫指標(biāo)為:

定理1.20[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則三角剖分圖T(G)的乘法度-基爾霍夫指標(biāo)為:

Kf*(T(G))=6Kf+(G)+6m2-2mn.

定理1.21[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則迭代三角剖分圖Tk(G)的乘法度-基爾霍夫指標(biāo)為:

定理1.22[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則迭代三角剖分圖Tk(G)的加法度-基爾霍夫指標(biāo)為:

定理1.23[16]設(shè)圖G為n(n≥2)個頂點(diǎn)和m條邊的連通圖， 則迭代三角剖分圖Tk(G)的基爾霍夫指標(biāo)為:

2016年， 劉曉剛等[17]給出了R-點(diǎn)聯(lián)和R-邊聯(lián)的電阻距離和基爾霍夫指標(biāo)的結(jié)果.

定理1.24[17]設(shè)圖G1的頂點(diǎn)數(shù)為n1邊數(shù)為m1， 圖G2的頂點(diǎn)數(shù)為n2， 則

定理1.25[17]設(shè)圖G1是n1個頂點(diǎn)和m1條邊上的r-正則圖(r>0)， 圖G2的頂點(diǎn)數(shù)為n2， 則

2016年， 盧鵬麗等[18]刻畫了Q-圖的電阻距離.劉群等[19]給出了R-點(diǎn)(邊)冠圖G1⊙G2(G1ΘG2)的基爾霍夫指標(biāo)的公式和下界， 其中G1為正則圖，G2為任意圖.

定理1.26[19]設(shè)G1是一個具有n1個頂點(diǎn)和m1條邊的r1-正則圖，G2是一個具有n2個頂點(diǎn)的任意圖， 則

定理1.27[19]設(shè)G1是一個具有n1個頂點(diǎn)和m1條邊的r1-正則圖，G2是一個具有n2個頂點(diǎn)的任意圖， 則

此外， Xie等[20]還得到了簡單連通圖迭代剖分圖的正規(guī)拉普拉斯譜， 作為應(yīng)用的一個例子， 計算了它們的乘法度-基爾霍夫指標(biāo)、 Kemeny常數(shù)和生成樹數(shù)的精確值.

定理1.28[20]對于任意n>0，sn(G)和sn-1(G)的乘法度-基爾霍夫指標(biāo)的關(guān)系如下：

Kf*(sn(G))=8Kf*(Sn-1(G))+2n(2r-1)E0，

因此，Kf*(sn(G))的一般表達(dá)式為:

其中r=E0-N0+1.

2021年， Sun等[21]刻畫了Q-點(diǎn)(邊)聯(lián)圖的電阻距離和基爾霍夫指標(biāo).

定理1.29[21]設(shè)G1和G2是兩個圖， 分別有n1(n2)個頂點(diǎn)m1(m2)條邊， 如果G1是一個d-正則圖， 那么G1QG2的基爾霍夫指標(biāo)為：

定理1.30[21]設(shè)G1和G2是兩個圖， 分別有n1(n2)個頂點(diǎn)m1(m2)條邊， 如果G1是一個d-正則圖， 那么G1QG2的基爾霍夫指標(biāo)為:

2 特殊圖類的(乘法度-)基爾霍夫指標(biāo)

因?yàn)閷τ谝话銏D的基爾霍夫指標(biāo)計算較困難， 所以只給出了一些特殊圖類的結(jié)果， 如Nordhaus-Gaddum[22]結(jié)論、 單圈圖的基爾霍夫指標(biāo)、 雙圈圖的基爾霍夫指標(biāo).

2.1 基爾霍夫指標(biāo)的Nordhaus-Gaddum類型結(jié)論

等式(在下界)成立當(dāng)且僅當(dāng)G是會議圖時.

雖然上界幾乎是最好的可能， 但它是不可達(dá)到的． 對于上界， 他們提出如下猜想：

2016年， Das和楊玉軍[25]考慮了3種基于電阻距離的圖不變量， 即基爾霍夫指標(biāo)、 加法度-基爾霍夫指標(biāo)和乘法度-基爾霍夫指標(biāo)， 給出了基于阻力距離的圖不變量的Nordhaus-Gaddum型的一些結(jié)果， 并建立了這些基爾霍夫指標(biāo)之間的關(guān)系.

定理2.5[25]設(shè)G是一個n階連通圖， 有m條邊， 最大度和最小度分別為Δ和δ， 則

2(n-1-δ)(2Δ+5-n)m.

定理2.6[25]設(shè)G是一個n階連通圖， 有m條邊， 最大度Δ

定理2.7[25]設(shè)G是一個n階連通圖， 有m條邊， 最大度和最小度分別為Δ和δ， 則

m(n-1-δ)2(2Δ+5-n).

定理2.8[25]設(shè)G是一個n階連通圖， 有m條邊， 最大度Δ>1， 最小度δ>1， 則

2018年， 楊玉軍等[26]利用電學(xué)和組合技術(shù)證明了文獻(xiàn)[24]的猜想除5個頂點(diǎn)上的樹圖外， 對所有圖都是正確的.

2.2 單圈圖的基爾霍夫指標(biāo)

若圖G只包含一個圈， 則稱為單圈圖． 為方便起見， 用G=U(Cl;T1，T2， …，Tl)表示， 其中Cl是G中唯一的圈． 設(shè)V(Cl)={v1，v2， …，vl}滿足對1≤i≤l，vi和vi+1相鄰， 對每個i， 令Ti為G中刪掉圈上除vi以外的所有點(diǎn)后得到的圖中包含vi的分支.

2008年， 楊玉軍等[27]研究了單圈圖的基爾霍夫指標(biāo)的界， 并給出了一些特殊單圈圖的基爾霍夫指標(biāo)公式． 如：

定理2.10[27]在所有的n個頂點(diǎn)的單圈圖中：

1)若n<8， 則Cn達(dá)到最小的基爾霍夫指標(biāo)；

定理2.11[27]對頂點(diǎn)數(shù)為n的單圈圖G：

2011年， 文獻(xiàn)[9]首次給出超基爾霍夫指標(biāo)的概念， 并給出了超Kirchhoff指標(biāo)的下界和上界， 同時確定了當(dāng)n≥5時具有最小、 次小和第三小超Kirchhoff指標(biāo)和最大、 次大和第三大超Kirchhoff指標(biāo)的n頂點(diǎn)單圈圖． 此外， 還確定了圈長為s(3≤s≤n)的n階單圈圖的最小和最大的超基爾霍夫指標(biāo)． 2012年， 文獻(xiàn)[8]首次給出加法度-基爾霍夫指標(biāo)的概念， 并刻畫了具有最小和次小加法度-基爾霍夫指標(biāo)的n個頂點(diǎn)的單圈圖.

一個單圈圖稱為是滿載單圈圖， 如果它的圈上的每個頂點(diǎn)的度都不小于3． 2009年， Guo等[28]確定了滿載單圈圖的基爾霍夫指標(biāo)的界并且刻畫了達(dá)到界的極值圖.

定理2.12[28]設(shè)G是頂點(diǎn)數(shù)n≥6的滿載單圈圖， 則

等式成立當(dāng)且僅當(dāng)n=8時G=U(C4;K2，K2，K2，K2)；當(dāng)n≠8時G=U(C3;K2，K2，Sn-4).

定理2.13[28]設(shè)G是頂點(diǎn)數(shù)n≥6的滿載單圈圖， 則

等式成立當(dāng)且僅當(dāng)G=U(C3;K2，K2，Pn-4).

2014年， Feng等[29]刻畫了滿載單圈圖的最大和最小乘法度-基爾霍夫指標(biāo)和仙人掌圖的最小乘法度-基爾霍夫指標(biāo).

定理2.14[29]設(shè)G是n(≥6)階的滿載單圈圖， 則

Kf*(U(C3;K2，K2，Sn-4))≤Kf*(G)≤Kf*(U(C3;K2，K2，Pn-4))，

左邊等號成立當(dāng)且僅當(dāng)G?U(C3;K2，K2，Sn-4)， 右邊等號成立當(dāng)且僅當(dāng)G?U(C3;K2，K2，Pn-4).

2020年， Qi等[30]確定了n階具有固定最大度的單圈圖的極大乘法度-基爾霍夫指標(biāo)， 以及n階單圈圖的前7個極大乘法度-基爾霍夫指標(biāo)， 并得到了相應(yīng)的極圖．

定理2.15[30]設(shè)U(n，Δ)為n個頂點(diǎn)最大度為Δ的單圈圖集合， 其中2≤Δ≤n-1， 設(shè)U′(n，Δ)是將C3的頂點(diǎn)與Δ頂點(diǎn)上的星中心連接， 路徑長度為n-Δ-2得到的單圈圖， 則

2020年， Chen等[31]得到了樹和單圈圖的補(bǔ)圖的Kirchhoff指標(biāo)的排序， 并給出了基爾霍夫指標(biāo)的一個上界．

定理2.16[31]設(shè)G是一個有n個頂點(diǎn)m條邊的連通圖， 則

2021年， Chen等[32]用單圈圖的剖分圖的匹配數(shù)刻畫了單圈圖的Kirchhoff指標(biāo).

定理2.17[32]對于任意n階連通單圈圖G， 它有一個Ck(圈長為k)， 其Kirchhoff指標(biāo)Kf(G)可以表示為：

其中m(S(G)，n-2)為單圈圖的剖分圖S(G)有n-2條邊的匹配數(shù)，S(G)-C2k為S(G)中刪除圈C2k的所有頂點(diǎn)而得到的無圈圖.

2.3 雙圈圖的基爾霍夫指標(biāo)

2009年， 張和平等[33]給出了恰有兩個圈的雙圈圖的基爾霍夫指標(biāo)的界， 并刻畫了達(dá)到界的極值圖．

定理2.18[33]在所有頂點(diǎn)數(shù)為n的恰有兩個圈的雙圈圖中：

定理2.19[33]對頂點(diǎn)數(shù)為n的恰有兩個圈的雙圈圖G：

等式成立當(dāng)且僅當(dāng)G?θ5(n-5， 0， 0， 0， 0).

2016年， 劉家保等[35]刻畫了具有最小基爾霍夫指標(biāo)的雙圈圖， 并確定了雙圈圖的基爾霍夫指標(biāo)的界．

定理2.22[35]設(shè)G∈βn， 則

2018年， Fei等[36]刻畫了n(≥6)階的雙圈圖的最大乘法度-基爾霍夫指標(biāo)和n(≥7)階的雙圈圖的次大乘法度-基爾霍夫指標(biāo).

定理2.23[36]設(shè)G是一個n(n≥6)階雙圈圖， 則

等式成立當(dāng)且僅當(dāng)G?Bn.

定理2.24[36]設(shè)G是一個n(n≥7)階雙圈圖且G不同構(gòu)于Bn， 則

特別地， 2013年Deng等[37]得到了由G的剖分圖的閉游動數(shù)表示的基爾霍夫指標(biāo)的表達(dá)式， 并確定了樹的補(bǔ)圖的基爾霍夫指標(biāo)的第一和第二最大值.

定理2.25[37]設(shè)G是一個具有n(n≥2)個頂點(diǎn)和m條邊的二部圖， 則

定理2.26[37]設(shè)T是一個有n(n≥2)個頂點(diǎn)的樹， 則

左邊等號成立當(dāng)且僅當(dāng)T是Sn時， 右邊等號成立當(dāng)且僅當(dāng)T是Pn.

3 基爾霍夫指標(biāo)的界

本節(jié)我們將確定一些圖的基爾霍夫指標(biāo)的界， 并且刻畫達(dá)到界的極值圖.

2010年， Palacios等[38]給出了n個頂點(diǎn)的d正則圖的基爾霍夫指標(biāo)上下界.

命題3.1[38]對任意n個頂點(diǎn)的k正則圖， 有

如果圖是二部圖， 則下界可進(jìn)一步改進(jìn)為：

2011年， Palacios等[39]給出了當(dāng)G是任意連通圖時， 基爾霍夫指標(biāo)的界為:

其中1=λ1(P)>λ2(P)≥…≥λn(P)≥-1是轉(zhuǎn)移矩陣P=D-1A的特征值.

2013年， Das[40]得到Kf(G)的下界取決于頂點(diǎn)數(shù)n， 最大度Δ， 生成樹數(shù)t:

等式成立當(dāng)且僅當(dāng)G?Kn或G?K1， n-1.

定理3.1[41]設(shè)G是一個具有n≥2個頂點(diǎn)和m條邊的簡單連通圖． 如果G是d-正則圖， 1≤d≤n-1， 則

定理3.2[42]設(shè)G是一個具有n≥3個頂點(diǎn)和m條邊的簡單連通圖， 則

定理3.3[42]設(shè)G是一個具有n≥3個頂點(diǎn)和m條邊的簡單連通圖， 則

等式成立當(dāng)且僅當(dāng)G?Kn.

定理3.4[42]設(shè)G是一個具有n≥2個頂點(diǎn)和m條邊的簡單連通圖， 則

等式成立當(dāng)且僅當(dāng)G?Kn.

定理3.5[42]設(shè)G是一個具有n≥2個頂點(diǎn)和m條邊的簡單連通圖， 對于任意具有性質(zhì)un-1≥k>0的實(shí)數(shù)k， 有

等式成立當(dāng)且僅當(dāng)k=n和G?Kn， 其中t為生成樹的個數(shù).

2012年， Yan等[43]刻畫了正則圖G的迭代線圖Lk(G)和迭代拋物線圖Ck(G)(或團(tuán)插入圖)的近似基爾霍夫指標(biāo).

定理3.6[43]設(shè)G是一個有n個頂點(diǎn)的連通的簡單r-正則圖， 則

定理3.7[43]設(shè)G是一個有n個頂點(diǎn)的連通的簡單r-正則圖， 則

2017年， 田貴賢[44]刻畫了正則圖的迭代全圖的近似(乘法度-)基爾霍夫指標(biāo)．

定理3.8[44]設(shè)G是一個有n個頂點(diǎn)m條邊的連通r-正則圖r≥2， 則

因此正則圖的迭代全圖的Kirchhoff指標(biāo)的近似值與G的結(jié)構(gòu)無關(guān)， 只與r和G的頂點(diǎn)數(shù)有關(guān)．

推論3.1[44]設(shè)G是一個有n個頂點(diǎn)m條邊的連通r-正則圖r≥2， 則

因此正則圖的迭代全圖的Kirchhoff指標(biāo)的近似值與G的結(jié)構(gòu)無關(guān)， 只與r和G的頂點(diǎn)數(shù)有關(guān)．

G的邊k-部圖是刪除使G成為k-部圖的最小邊數(shù)， 用lk(G)表示． 設(shè)m≤n-k，n，m，k是具有n個頂點(diǎn)且lk(G)≤m的圖族， 即

ψn， m， k={G: |V(G)|=n，lk(G)≤m}，

如果k=2， 稱為G的邊二部圖.

2017年， He等[45]給出了關(guān)于ψn， m， k的Kirchhoff指標(biāo)最小化的第一個結(jié)果， 其中刻畫了ψn， m， 2中的最優(yōu)圖.

2019年， Huang等[46]給出了給定邊k-部圖的最小基爾霍夫指標(biāo)的理論和計算方法.

這里設(shè)n=pk+q， 其中p，q是非負(fù)整數(shù)， 且0≤q

4 基爾霍夫指標(biāo)的應(yīng)用

在化學(xué)圖論中， 一些化合物可以用化學(xué)圖來表示， 其中頂點(diǎn)代表原子， 而邊代表原子間的共價鍵． 此外， 預(yù)測化合物的物理化學(xué)性質(zhì)一直是理論化學(xué)的研究熱點(diǎn)， 因此下面列出一些線性鏈網(wǎng)絡(luò)圖的電阻距離和基爾霍夫指標(biāo)的研究結(jié)果.

4.1 線性鏈和網(wǎng)絡(luò)圖的基爾霍夫指標(biāo)

近年來， 相關(guān)學(xué)者已經(jīng)計算了許多線性鏈的電阻距離、 基爾霍夫指標(biāo)和加法度(乘法度-)基爾霍夫指標(biāo)． 例如， 線性多邊形鏈、 線性六角形鏈、 六角形鏈、 梯形圖、 梯形鏈、 線性多項(xiàng)式鏈等.

2020年， Zhang等[47]刻畫了隨機(jī)聚苯乙烯鏈的舒爾茨指標(biāo)、 古特曼指標(biāo)、 乘法度-基爾霍夫指標(biāo)和加法度-基爾霍夫指標(biāo)的期望值.

定理4.1[47]設(shè)n≥1， 則隨機(jī)聚苯乙烯鏈Gn的乘法度-基爾霍夫指標(biāo)的期望值為：

定理4.2[47]設(shè)n≥1， 則隨機(jī)聚苯乙烯鏈Gn的加法度-基爾霍夫指標(biāo)的期望值為：

2021年， Zhang等[48]建立了方差的顯式解析表達(dá)式， 以及隨機(jī)聚苯乙烯鏈的古特曼指標(biāo)、 舒爾茨指標(biāo)、 可乘度基爾霍夫指標(biāo)和可加度基爾霍夫指標(biāo)， 并且證明了隨機(jī)聚苯乙烯鏈的這4個指標(biāo)是漸近正態(tài)分布． 李佳建和王維忠[49]通過求解差分方程， 建立了隨機(jī)多邊形鏈中基爾霍夫指標(biāo)、 乘法度-基爾霍夫指標(biāo)和加法度-基爾霍夫指標(biāo)期望值的顯式解析表達(dá)式.

定理4.3[49]設(shè)PCn是一個n長的(2k+1)-多邊形鏈， 其中k≥1且n≥2， 則

定理4.4[49]設(shè)PCn是一個n長的(2k+1)-多邊形鏈， 其中k≥1且n≥2， 則

定理4.5[49]設(shè)PCn是一個n長的(2k+1)-多邊形鏈， 其中k≥1且n≥2， 則

定理4.6[49]設(shè)PCn是一個n長的2k-多邊形鏈， 其中k≥2且n≥2， 則

定理4.7[49]設(shè)PCn是一個n長的2k-多邊形鏈， 其中k≥2且n≥2， 則

定理4.8[49]設(shè)PCn是一個n長的2k-多邊形鏈， 其中k≥2且n≥2， 則

2020年， 彭穎君[50]研究了線性六四角鏈、 線性八四對角鏈、 M?bius線性六四環(huán)鏈的(乘法度-)基爾霍夫指標(biāo).

近年來， 關(guān)于網(wǎng)絡(luò)圖的基爾霍夫指標(biāo)的研究吸引了許多研究者的注意， 如：有線網(wǎng)絡(luò)、 集群網(wǎng)絡(luò)、 電暈或星團(tuán)網(wǎng)絡(luò)、 星形和錐形網(wǎng)絡(luò)等． 特別地， 2020年， Huang等[51]得到了線性六邊形(圓柱形)鏈的電阻距離和基爾霍夫指標(biāo)公式， 并給出了線性六邊形(圓柱形)鏈電阻距離的單調(diào)性和一些漸近性質(zhì)；Sardar等[52]得到了鏈硅酸鹽網(wǎng)絡(luò)和環(huán)硅酸鹽網(wǎng)絡(luò)的電阻距離和基爾霍夫指標(biāo)公式． 2021年， Palacios等[53]刻畫了高對稱圖簇的Kemeny常數(shù)和基爾霍夫指標(biāo)公式；Kook等[54]給出了單純網(wǎng)絡(luò)的基爾霍夫指標(biāo)的計算公式， 利用此公式得到了代數(shù)連通性和基爾霍夫指標(biāo)的高維類似物的一個不等式， 并提出這些量作為單純復(fù)形魯棒性的度量.

4.2 基爾霍夫指標(biāo)與其他指標(biāo)的關(guān)系

2006年， Gutman和周波[55]定義了圖G的拉普拉斯能量：

2008年， 柳柏濂等[56]定義了圖G的擬拉普拉斯能量：

2012年， Das等[57]比較了Kf(G)和LEL(G)， 并建立了LEL(G)

LEL(G)

LEL(G)

2018年， Das和Gutman[58]得到了擬拉普拉斯能量LEL與基爾霍夫指標(biāo)Kf、 拉普拉斯能量LE與基爾霍夫指標(biāo)Kf的兩個關(guān)系.

定理4.11[58]設(shè)G是一個有m條邊的n(>2)階連通圖，Δ為頂點(diǎn)最大度， 則

等式成立當(dāng)且僅當(dāng)G?Kn或G?K1， n-1.

定理4.12[58]設(shè)G是一個有m條邊的n(>2)階連通圖， 則

其中u1≥k≥Δ+1(Δ為頂點(diǎn)最大度).

定理4.13[58]設(shè)G是一個有m條邊的n階連通圖， 則

定理4.14[58]設(shè)G是一個有m條邊的n(>2)階連通圖， 則

Kf(G)(M1(G)+2m)≥nLEL2(G)，

等式成立當(dāng)且僅當(dāng)G?Kn.

定理4.15[59]設(shè)G是一個有m條邊的n(≥2)階連通圖， 則

定理4.16[59]設(shè)G是一個有m條邊的n(≥2)階連通圖， 則

nLEL4(G)≤8m3Kf(G)，

等式成立當(dāng)且僅當(dāng)G?Kn.

定理4.17[59]設(shè)G是一個有m條邊的n(≥2)階連通圖， 則

等式成立當(dāng)且僅當(dāng)G?Kn， 或G?K1， n-1， 或G?Γd.

定理4.18[59]設(shè)G是一個有m條邊的n(≥2)階連通圖， 則

等式成立當(dāng)且僅當(dāng)G?Kn， 或G?K1， n-1， 或G?Γd.

定理4.19[59]設(shè)G是一個有m條邊的n(≥2)階連通圖， 則

8m3(Kf(G)+1)-n2(n-1)S2(G)≥4n2(n-1)m2，

等式成立當(dāng)且僅當(dāng)G?Kn或G?Γd.

定理4.20[59]設(shè)G是一個有m條邊的n(≥2)階連通圖， 則

等式成立當(dāng)且僅當(dāng)G是正則圖.

對于一些特殊圖類， 如賦權(quán)圖、 賦權(quán)輪圖、 具有固定割頂點(diǎn)數(shù)的圖、 完全多部圖、 莫比烏斯階梯(Mn=C2n(1，n))和棱鏡圖(Prn=Cn×P2)[60]的Kirchhoff指標(biāo)也分別得到了刻畫. 特別地， 2018年Mitsuhashi等[61]首次提出加權(quán)基爾霍夫指標(biāo)， 并給出正則覆蓋圖的基爾霍夫指標(biāo)；2021年， Lin等[62]給出了混合圖的埃爾米特基爾霍夫指標(biāo)與魯棒性；2017年， 劉家保[63]在《電阻距離和基爾霍夫指標(biāo)的研究》中刻畫了雙圈圖、 仙人掌圖、 超立方體網(wǎng)絡(luò)等的基爾霍夫指標(biāo)， 并得到了一些新的有意義的結(jié)果.

定理4.21[60]莫比烏斯階梯(Mn=C2n(1，n))的基爾霍夫指標(biāo)為：

定理4.22[60]棱鏡圖(Prn=Cn×P2)的基爾霍夫指標(biāo)為：

5 一些猜想和未解決的問題

1)2020年， 文獻(xiàn)[46]研究了在n，m，k中求最小基爾霍夫指標(biāo)的問題， 即求最小值給定k-分布性圖的基爾霍夫指標(biāo)． 該文章從理論上部分地解決了這個問題， 并提出了采用包括窮舉搜索和3種計算策略在內(nèi)的算法來解決問題． 然而， 在n，m，k中具有最小基爾霍夫指標(biāo)的最優(yōu)圖的完全刻畫問題尚有待進(jìn)一步解決．

2)文獻(xiàn)[50]的最后提出了一些尚待解決的問題:

(a)可以進(jìn)一步考慮對有一個割點(diǎn)的線性六四角鏈的分子圖的拉普拉斯譜以及基爾霍夫指標(biāo)和支撐數(shù)目的研究；

(b)可以進(jìn)一步考慮對M?bius線性八四對角鏈的拉普拉斯譜及基爾霍夫指標(biāo)和支撐樹數(shù)目， 以及正規(guī)拉普拉斯譜及度基爾霍夫指標(biāo)與支撐數(shù)目的研究;

(c)可以進(jìn)一步對四邊形、 六邊形及八邊形在一個線性鏈中同時出現(xiàn)或?qū)Ψ蔷€性及其他邊形的角鏈類型的相關(guān)問題進(jìn)一步研究.

3)在第2節(jié)中， 就單圈圖而言， 可以考慮加一些限制條件的單圈圖， 如具有完美匹配的單圈圖和確定懸掛點(diǎn)個數(shù)的單圈圖． 對于雙圈圖， 可以繼續(xù)考慮具有3個圈的雙圈圖的基爾霍夫指標(biāo).

4)2021年， 文獻(xiàn)[54]中提出了一個開放的問題， 并給出下列恒等式的組合證明：

5)2020年，文獻(xiàn)[64]中的定理6認(rèn)為在所有具有任意固定直徑的二部圖中，基爾霍夫指標(biāo)最小和最大的圖可以用同樣的方法確定．但是在所有直徑大于3的二部圖中刻畫第二小、第三小以及第二大和第三大的基爾霍夫指標(biāo)將是一個非常具有挑戰(zhàn)性的問題.