伊佳茹，雷英杰

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

給定直徑的單圈圖的Harary指數(shù)

伊佳茹，雷英杰

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

連通圖G的Harary指數(shù)是指圖G中所有點(diǎn)對(duì)的距離的倒數(shù)之和。主要研究固定直徑的單圈圖的極大Harary指數(shù)及相對(duì)應(yīng)的極圖。特別地,當(dāng)4≤d≤n-3,且d≡0(mod2)時(shí),得到第二大Harary指數(shù)的極圖。

Harary指數(shù)；直徑；單圈圖；極圖

Harary指數(shù)是一種重要的化學(xué)類(lèi)拓?fù)渲笖?shù)。該指數(shù)被提出之后,國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了深入的研究[1-10]，其中：文獻(xiàn)[1]研究了給定懸掛點(diǎn)和階數(shù)的單圈圖的極大Harary指數(shù)；文獻(xiàn)[3]找到了固定直徑,匹配數(shù)和獨(dú)立點(diǎn)集的簡(jiǎn)單圖的極小Harary指數(shù)以及其所對(duì)應(yīng)的極圖；文獻(xiàn)[4]得到了固定直徑的樹(shù)的第二大Harary指數(shù)以及相對(duì)應(yīng)的極圖。

1 引理及相關(guān)證明

引理2[13]令H是一個(gè)連通圖,Tl表示階為l的樹(shù),且V(H)∩V(Tl)={v},則有

H(HvTl)≤H(HvK1,l-1)

當(dāng)且僅當(dāng)HvTl?HvK1,l-1等號(hào)成立。引理2是文獻(xiàn)[14]中定理4的特殊情況。

引理4 令G是一個(gè)連通圖,uv∈E(G),Gp,q(u,v)是由圖G分別在點(diǎn)u連接一條長(zhǎng)為P的懸掛路,點(diǎn)v連接一條長(zhǎng)為q的懸掛路所得到的。若p≥q≥1,則有

H(Gp,q(u,v))>H(Gp+1,q-1(u,v))

證明記G0=G-{u,v}；懸掛路分別為：P=uu1u2…up,Q=vv1v2…vq。將G0圖中的點(diǎn)分成3部分：

V1={vid(vi,u)=d(vi,v)}

V2={vid(vi,u)=d(vi,v)+1}

V3={vid(vi,u)+1=d(vi,v)}

則有：

當(dāng)p≥q≥1時(shí),有

由此易知H(Gp,q(u,v))>H(Gp+1,q-1(u,v))。證明完畢。

圖和

則有

圖2 U0的d+2階單圈圖

論斷1 若i≠d+2,且pi>1,則i∈{k,k+1}。

采用反證法：若i≠d+2,則i?{k,k+1}?？紤]其對(duì)稱性,只需要考慮k+1

1) 當(dāng)k

V1={v1,v2,…,vk}；V2={vk+2,vk+3,…,vd+1}；V3={u1,u2,…,upi}

對(duì)vx∈V1,vy∈V2,vz∈V3,有如下關(guān)系：

dG1(vx,vd+2)-dG(vx,vd+2)=1

dG1(vy,vd+2)-dG(vy,vd+2)=-1

dG1(vz,vd+2)-dG(vz,vd+2)=-1

則有

顯然有H(G1)-H(G)>0。記圈C=vk1vk1+1vd+2vk1(k1=k+1)是圖G1的圈。若vk1+1即為vi,則G1中的點(diǎn)vk1+1上有懸掛點(diǎn),H(G1)>H(G),矛盾。若k1+1

2) 當(dāng)k≥d-k時(shí),有i-1>k≥d-k≥d-(i-2)。構(gòu)造圖G1=G-viu1-viu2-…-viupi+vi-1u1+…+vi-1upi,同理可得

由1)和2)可知：論斷1得證。

論斷2i≠d+2。

采用反證法：若i=d+2,構(gòu)造圖G*=G-vd+2u1-…-vd+2upi+vku1+…+vkupi。同理可得：

顯然H(G*)>H(G),矛盾,論斷2得證。

論斷3k≠d。

采用反證法：若k=d,構(gòu)造圖G*=G-vd+1vd+2+vd-1vd+2,同理可得：

顯然H(G*)>H(G),矛盾,論斷3得證。

由引理6和引理7,引理8顯然成立。

2 主要結(jié)論

論斷5V(Cq)∩V(Pd+1)≠?。

采用反證法：假設(shè)V(Cq)∩V(Pd+1)=?,因?yàn)镚連通圖,則一定存在一條路Q=vivkvk+1…vl-1vl連接圈和誘導(dǎo)路,vi∈V(Cq),vl∈V(Pd+1)且vk…vl-1∈V(G)/(V(Cq)∪V(Pd+1)),令u1,u2,…,ud(vl)-1∈N(vl)/{vl-1}。構(gòu)造圖G*=G-vlu1-…-vlud(vl)-1+viu1+…+viud(vl)-1,由引理1可得H(G*)>H(G),矛盾。

論斷6 對(duì)于v∈V(G)/(V(Cq)∪V(Pd+1)),有d(v)=1,且這些點(diǎn)都懸掛在圈或路的同一個(gè)點(diǎn)上。

證明由引理2和引理1,對(duì)于v∈V(G)/(V(Cq)∪V(Pd+1))的所有點(diǎn),一定以樹(shù)的形式連接在圈或者路上邊,論斷6得證。

論斷7k≠l。

采用反證法：假設(shè)k=l,其中vd+2、vk+1、vk+2一定存在。

記u1,u2,…,ud(vd+2)-1∈NG(vd+2)/vk,懸掛點(diǎn)的鄰點(diǎn)為vm,懸掛點(diǎn)的個(gè)數(shù)為pm。構(gòu)造圖G*=G-vd+2u1-…-vd+2ud(vd+2)-1+vk+1u1+…+vk+1ud(vd+2)-1。

記V1=vi:vi∈Cq/{vk}且dvi,vd+2

dG*(vx,vd+2)-dG(vx,vd+2)=2；dG*(vx,vz)-dG(vx,vz)=-2；

dG*(vy,vd+2)-dG(vy,vd+2)=1；dG*(vy,vz)-dG(vy,vz)=-1

當(dāng)vm∈V1時(shí)有

記：

當(dāng)vm∈V2時(shí)有

當(dāng)vm∈V3時(shí)有

當(dāng)vm為vd+2時(shí)有

綜上可得H(G*)>H(G),矛盾。若圍長(zhǎng)g為偶數(shù),同理H(G*)>H(G),論斷7得證。

論斷8 若l=k+1,那么s-d=2；若l≥k+2,那么s-d=l-k。

采用反證法：否則s-d>l-k≥3,其中vd+3一定存在，且l≥k+2,則vl-1一定存在。 記u1，u2,…,udG(vd+2)-1∈NG(vd+2)/{vl}。構(gòu)造圖G*=G-vd+2u1-vd+2u2-…-vd+2udG(vd+2)-1+vlu1+vlu2+…+vludG(vd+2)-1。記V1={vi:vi∈Cq/{vk,vk+1,…,vl,vd+2},且d(vi,vk)

dG*(vx,vy)-dG(vx,vy)=-1

若圖G中的圈為偶圈，記V3={vi:vi∈Cq/{vk,vk+1,…,vl},且dG*(vi,vd+2)

dG*vz,vm-dGvz,vm=-1

顯然有H(G*)>H(G),矛盾。

dG*vz,vm-dGvz,vm=-1

顯然有H(G*)>H(G),矛盾。論斷8得證。

論斷9l=k+1。

證明假設(shè)l≠k+1,由論斷4可知s-d=l-k,不妨設(shè)懸掛點(diǎn)都在Pd+1的點(diǎn)vi上,懸掛點(diǎn)為u1,u2,…,um,由于對(duì)稱性,只對(duì)vl和vi的位置進(jìn)行討論。

1) 若l=i,構(gòu)造G*=G-vlvd+2-vd+2vd+3-vlu1-…-vlum+vl-1vd+2+vl-1vd+3+vl-1u1+vl-1um，則有

由于l-k≥5,顯然H(G*)>H(G)成立,矛盾。

2) 若i>l,構(gòu)造圖G*=G-vlvd+2-vd+2vd+3+vl-1vd+2+vl-1vd+3,則有

得H(G*)>H(G),矛盾。

3) 若k

得H(G*)>H(G),矛盾。

由定理1和引理9,以下定理顯然成立：

[1] CAI G X，GUIDONG Y U，XING B H.Harary index of unicyclic graphs with n vertices and k pendent vertices[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,2015(1)：120-125.

[2] XU Kexiang,KINKAR C D.On harary index of graphs[J].Discrete Applied Mathematics,2011,159： 1631-1640.

[3] FENG L，LAN Y，LIU W，et al.Minimal Harary Index of Graphs with Small Parameters[J].MATCH Commun.Math.Comput.Chem.2016，76(1)：23-42.

[4] 肖金環(huán),趙飚.固定直徑的樹(shù)的Harary指數(shù)[J].曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2014(3)：30- 34.

[5] HE Changxing，CHEN Ping,WUA Baofeng.The Harary Index of a Graph Under Perturabation[J].Discrete Math- matics,Algorithms and Applications,2010,2(2):247-255.

[6] XING Baohua,CAI Gaixiang.The Wiener index of trees with prescribed diameter[J].Operations Research Transactions,2011,15(4)：36-44.

[8] LI Xiaoxia.On the extremal wiener index of some graphs[J].Operations Research Transactions,2010,14(2)：55-60.

[9] CHEN Yahong,ZHANG Xiaodong.The Wiener index of unicycle graphs with girth and the matching number[J].Mathematics,2011(2)：1-15.

[11] BONDY A，MMURTY U S R.Graph Theory with Application[M].New York：Macmillan Press,1976.

[12] XU Kexiang,NENAD T.Hyper-wiener and Harary indices of graphs with cut edges[J].Utilitas Math，2011,84：153-163.

[13] 陳單單.單圈圖的Harary指數(shù)[D].長(zhǎng)沙：湖南師范大學(xué),2009.

[14] HE C X，CHEN P，WU B F.The Harary index of a graph under perturbation[J].Discrete Mathematics Algorithms & Applications，2010，2(2)：247-255.

(責(zé)任編輯劉 舸)

OntheHararyIndexofUnicycleGraphswithGivenDiameter

YI Jiaru

(School of Science, North University of China, Taiyuan 030051, China)

The Harary index is defined as the sum of reciprocals of distance over all pairs of vertices of a connected graph.This paper gives the largest Harary index of unicycle graphs with given diameter and characterizes the extreme graphs attaining the upper bound. Specially, we also obtained the second largest extreme graphs when 4≤d≤n-3 andd≡0(mod2).

Harary index；diameter；unicycle graph；extreme graph

2017-05-12

國(guó)家自然科學(xué)基金資助項(xiàng)目(11301489)

伊佳茹(1993—)，女，山西人，碩士研究生，主要從事組合數(shù)學(xué)研究，E-mail:1045161925@qq.com。

伊佳茹，雷英杰.給定直徑的單圈圖的Harary指數(shù)[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2017(11):204-210.

formatYI Jiaru, LEI Yingjie.On the Harary Index of Unicycle Graphs with Given Diameter[J].Journal of Chongqing University of Technology(Natural Science)，2017(11):204-210.

10.3969/j.issn.1674-8425(z).2017.11.031

O157.5

A

1674-8425(2017)11-0204-07