曹瑞云，雷英杰，趙孟孟

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

拓?fù)渲笖?shù)是從化合物的結(jié)構(gòu)圖衍生出來(lái)的一種數(shù)學(xué)不變量，其中最早被研究的是Wiener指數(shù)、Harary指數(shù)等，這些指數(shù)大多是基于圖中頂點(diǎn)之間的距離或者點(diǎn)度研究的。由于圖論在物理學(xué)中有很好的應(yīng)用，本文研究一種基于電阻距離的指數(shù)——Resistance-Harary指數(shù)。這類指數(shù)目前研究較多的是Kirchhoff指數(shù)，它表示為

類似Wiener指數(shù)和Harary指數(shù)之間的關(guān)系，與Kirchhoff指數(shù)對(duì)應(yīng)的指數(shù)就是Resistance-Harary指數(shù)。目前關(guān)于電阻距離以及一些特殊圖的Kirchhoff指數(shù)的研究已有很多，而關(guān)于Resistance-Harary指數(shù)的研究卻并不多。

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

1 Resistance-Harary指數(shù)的計(jì)算

本文涉及的圖都是連通的簡(jiǎn)單無(wú)向圖。設(shè)圖G是連通的簡(jiǎn)單無(wú)向圖，將圖G中的每條邊用一個(gè)單位電阻來(lái)代替，構(gòu)造出相應(yīng)的電網(wǎng)絡(luò)N，電網(wǎng)絡(luò)N中任意兩點(diǎn)x、y之間的等效電阻即為圖G中相應(yīng)節(jié)點(diǎn)之間的電阻距離，用rG(x,y)表示。圖G的Resistance-Harary指數(shù)用RH(G)表示，它是指圖G中所有點(diǎn)對(duì)之間的電阻距離的倒數(shù)之和，即

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

定理1 設(shè)Cg是g(g≥3)長(zhǎng)圈，對(duì)于任意頂點(diǎn)v∈V(Cg)，則圈上其余點(diǎn)到v的電阻距離為

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

證明將圈圖看作相應(yīng)的電網(wǎng)絡(luò)結(jié)構(gòu)，則圈上每條邊都是一個(gè)單位電阻，現(xiàn)設(shè)圈上一頂點(diǎn)到v的電阻為i，則剩余部分的電阻為g-i，由歐姆定律易知

定理2 圈Cg的Resistance-Harary指數(shù)計(jì)算公式為

證明在定理1的基礎(chǔ)上可知，圈上除去v的其余各頂點(diǎn)到v的電阻距離的倒數(shù)之和為

因此容易得出圈Cg上任意2點(diǎn)的電阻距離倒數(shù)之和即Resistance-Harary指數(shù)，其計(jì)算公式為

在簡(jiǎn)單連通的無(wú)圈圖中，由歐姆定律計(jì)算可知圖中頂點(diǎn)之間的電阻距離和距離是相等的，也就是說(shuō)此時(shí)圖的Resistance-Harary指數(shù)和Harary指數(shù)是相同的，則有以下定理。

2 引理

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

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

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

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

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

證明根據(jù)圖的Resistance-Harary指數(shù)的計(jì)算公式，

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 結(jié)論

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

1) 當(dāng)r(x,u)

2) 當(dāng)r(x,v)

圖2 G,G′和G″

證明根據(jù)Resistance-Harary指數(shù)的定義，先寫(xiě)出圖G、G′和G″的相應(yīng)指數(shù)計(jì)算式：

(1)

(2)

(3)

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

對(duì)于任意x∈H，當(dāng)r(x,u)

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

證明假設(shè)圈Cg上存在一點(diǎn)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上的點(diǎn)。設(shè)

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

圖3 G和G*

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

參考文獻(xiàn)：

[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] 蔡改香,余桂東,邢抱花.具有個(gè)懸掛點(diǎn)的階單圈圖的Harary指數(shù)[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2015(1):120-125.

[13] 邢抱花.關(guān)于雙圈圖的Harary指數(shù)[J].菏澤學(xué)院學(xué)報(bào),2015,37(5):14-16.

[14] 蔡改香,邢抱花,余桂東.三圈圖的Harary指數(shù)[J].運(yùn)籌學(xué)學(xué)報(bào),2015,19(2):45-53.