給定k個懸掛點的單圈圖的極大Resistance-Harary指數

曹瑞云，雷英杰，趙孟孟

(中北大學 理學院， 太原 030051)

拓撲指數是從化合物的結構圖衍生出來的一種數學不變量，其中最早被研究的是Wiener指數、Harary指數等，這些指數大多是基于圖中頂點之間的距離或者點度研究的。由于圖論在物理學中有很好的應用，本文研究一種基于電阻距離的指數——Resistance-Harary指數。這類指數目前研究較多的是Kirchhoff指數，它表示為

類似Wiener指數和Harary指數之間的關系，與Kirchhoff指數對應的指數就是Resistance-Harary指數。目前關于電阻距離以及一些特殊圖的Kirchhoff指數的研究已有很多，而關于Resistance-Harary指數的研究卻并不多。

單圈圖是只含一個圈的圖，設圖G是簡單無向圖，頂點集為V(G)，邊集為E(G)。設v∈V(G)，G中與點v關聯的邊的條數稱為v的度，記為dG(v)或者d(v)。度為1的點叫作懸掛點。設u∈V(G)，則N(u)表示與u相鄰的點組成的集合。G-u表示圖G刪掉頂點u以及與u關聯的所有邊得到的子圖。Pn、Cn分別表示n階路、n長圈，T表示樹。另外用Un,g,k表示有n個頂點、k個懸掛點且圍長是g的單圈圖類，其中3≤g≤n-1，1≤k≤n-3。本文將給出k個懸掛點的具有極大Resistance-Harary指數的單圈圖類。

1 Resistance-Harary指數的計算

本文涉及的圖都是連通的簡單無向圖。設圖G是連通的簡單無向圖，將圖G中的每條邊用一個單位電阻來代替，構造出相應的電網絡N，電網絡N中任意兩點x、y之間的等效電阻即為圖G中相應節點之間的電阻距離，用rG(x,y)表示。圖G的Resistance-Harary指數用RH(G)表示，它是指圖G中所有點對之間的電阻距離的倒數之和，即

其中rG(u,v)是指圖G中頂點u、v之間的電阻距離。

定理1 設Cg是g(g≥3)長圈，對于任意頂點v∈V(Cg)，則圈上其余點到v的電阻距離為

其中i=1,2,…,g-1。

證明將圈圖看作相應的電網絡結構，則圈上每條邊都是一個單位電阻，現設圈上一頂點到v的電阻為i，則剩余部分的電阻為g-i，由歐姆定律易知

定理2 圈Cg的Resistance-Harary指數計算公式為

證明在定理1的基礎上可知，圈上除去v的其余各頂點到v的電阻距離的倒數之和為

因此容易得出圈Cg上任意2點的電阻距離倒數之和即Resistance-Harary指數，其計算公式為

在簡單連通的無圈圖中，由歐姆定律計算可知圖中頂點之間的電阻距離和距離是相等的，也就是說此時圖的Resistance-Harary指數和Harary指數是相同的，則有以下定理。

2 引理

引理1[6]設點x是連通圖G的割點，其中a和b是處于G中不同連通分支且不同于x的2個頂點，則有

rG(a,b)=rG(a,x)+rG(x,b)

引理2 設Cg是g長圈，g≥3且w是圈上一點，Ca,b(見圖1)表示在圈Cg的w點上添加2條懸掛路，分別為P:wu1u2…ua和Q:wv1v2…vb，其中u1,u2,…,ua和v1,v2,…,vb是不同的點。若a≥b≥1，則

HR(Ca,b)>HR(Ca+1,b-1)

圖1 圖Ca,b和Ca+1,b-1

證明根據圖的Resistance-Harary指數的計算公式，

HR(Ca,b)-HR(Ca+1,b-1)=

由于a≥b≥1，則HR(Ca,b)-HR(Ca+1,b-1)>0，可證明HR(Ca,b)>HR(Ca+1,b-1)。

3 結論

定理4 設H、X、Y是3個互不相交的連通圖。設u、v為H上2點，u0、v0分別為X、Y上的點。若將H的u點與X的u0粘合，v點與Y的v0點粘合得到的圖記作G，將H的u點與X的u0以及Y的v0點粘合得到的圖記作G′，將H的v點與X的u0以及Y的v0點粘合得到的圖記作G″(見圖2)，則對于任意x∈H，有以下結論：

1) 當r(x,u)

2) 當r(x,v)

圖2 G,G′和G″

證明根據Resistance-Harary指數的定義，先寫出圖G、G′和G″的相應指數計算式：

(1)

(2)

(3)

由于G中Y上任一點到v的電阻距離與G′中Y上這一點到u的電阻距離相等，G中X上任一點到u的電阻距離與G″中X上這一點到v的電阻距離相等，為簡便，式(1)與式(2)(3)分別作差可寫為：

對于任意x∈H，當r(x,u)

定理5 設G∈Un,g,k，HR(G)達到極大，則有唯一的點w∈V(Cg)，使dG(w)≥3。

證明假設圈Cg上存在一點z且z≠w，dG(z)≥3。N(w)={w1,w2,u1,u2,…,us}，

N(z)={z1,z2,v1,v2,…,vt}，其中w1,w2,z1,z2均為圈Cg上的點。設

利用反證法，假設存在一點z∈V(T){w}，且d(z)≥3。設N(z)={z1,z2,…,zs}，N(w)={w1,w2,…,wt}，其中z1和w3在w到z的路上，w1,w2∈V(Cg)，s≥3，t≥3?，F設G*=G-{zz3,zz4,…,zzs}+{wz3,wz4,…,wzs}，G和G*見圖3，顯然根據Resistance-Harary指數的計算方法，對于任意的x∈G-{w4,…,wt,z3,…,zs}，均有r(x,w)RH(G)，與題設中HR(G)達到極大矛盾，由此證明對于任意一點v∈V(T)，v≠w，都有d(v)≤2，因此G是在Cg上的w點粘合k條懸掛路得到的。最后證明G?BUn,g,k，即這k條懸掛路差不多相等時，HR(G)達到極大。

圖3 G和G*

同樣利用反證法，假設存在2條路Pk和Pl，k-l≥2，l≥2，Pk:u1,u2,…,uk，Pl:v1,v2,…,vl,其中，u1=v1=w。設G**=G-{uk-1uk}+{vluk}，則由引理2可得，RH(G**)>RH(G)，與題設矛盾。

參考文獻：

[1] BONDY J A.Graph theory with applications[J].Journal of the Operational Research Society,1977.

[2] CHEN Shubo,GUO Zhijun,ZENG Ting,et al.On the resistance-Harary index of unicyclic graphs[J].MATCH Commun Math Comput Chem，2017(78)：189-198.

[3] XU K,LIU M,DAS K C,et al.A survey on graphs extremal with respect to distance-based topological indices[J].MATCH Commun Math Comput Chem， 2014(71)：461-508.

[6] ZHANG H,JIANG X,YANG Y.Bicyclic graphs with extremal Kirchhoff index[J].MATCH Commun Math Comput Chem，2009(61)：697-712.

[7] YANG Y.On a new cyclicity measure of graphs-The global cyclicity index[J].Discr Appl Math，2014(172)：88-97.

[8] XI L F.Lipschitz equivalence of dust-like self-similar sets[J].Math Z,2010,266(3):683-691.

[9] XU K,DAS K C.Extremal unicyclic and bicyclic graphs with respect to Harary Index[J].Bull Malays Math Sci Soc,2010,36(2):373-383.

[10] BONCHEV D,BALABAN A T,LIU X,et al.Molecular cyclicity and centricity of polycyclic graphs I.Cyclicity based on resistance distances or reciprocal distances[J].Int J Quantum Chem,1994，50(1)：1-20.

[11] KLEIN D J,IVANCIUC O.Graph cyclicity,excess conductance,and resistance decit[J].J Math Chem， 2001,30(3):271-287.

[12] 蔡改香,余桂東,邢抱花.具有個懸掛點的階單圈圖的Harary指數[J].華東師范大學學報(自然科學版),2015(1):120-125.

[13] 邢抱花.關于雙圈圖的Harary指數[J].菏澤學院學報,2015,37(5):14-16.

[14] 蔡改香,邢抱花,余桂東.三圈圖的Harary指數[J].運籌學學報,2015,19(2):45-53.