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

伊佳茹，雷英杰

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

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

伊佳茹，雷英杰

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

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

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

Harary指數(shù)是一種重要的化學類拓撲指數(shù)。該指數(shù)被提出之后,國內(nèi)外學者對其進行了深入的研究[1-10]，其中：文獻[1]研究了給定懸掛點和階數(shù)的單圈圖的極大Harary指數(shù)；文獻[3]找到了固定直徑,匹配數(shù)和獨立點集的簡單圖的極小Harary指數(shù)以及其所對應的極圖；文獻[4]得到了固定直徑的樹的第二大Harary指數(shù)以及相對應的極圖。

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

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

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

當且僅當HvTl?HvK1,l-1等號成立。引理2是文獻[14]中定理4的特殊情況。

引理4 令G是一個連通圖,uv∈E(G),Gp,q(u,v)是由圖G分別在點u連接一條長為P的懸掛路,點v連接一條長為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圖中的點分成3部分：

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

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

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

則有：

當p≥q≥1時,有

由此易知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}?？紤]其對稱性,只需要考慮k+1

1) 當k

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

對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中的點vk1+1上有懸掛點,H(G1)>H(G),矛盾。若k1+1

2) 當k≥d-k時,有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)=?,因為G連通圖,則一定存在一條路Q=vivkvk+1…vl-1vl連接圈和誘導路,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 對于v∈V(G)/(V(Cq)∪V(Pd+1)),有d(v)=1,且這些點都懸掛在圈或路的同一個點上。

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

論斷7k≠l。

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

記u1,u2,…,ud(vd+2)-1∈NG(vd+2)/vk,懸掛點的鄰點為vm,懸掛點的個數(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

當vm∈V1時有

記：

當vm∈V2時有

當vm∈V3時有

當vm為vd+2時有

綜上可得H(G*)>H(G),矛盾。若圍長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è)懸掛點都在Pd+1的點vi上,懸掛點為u1,u2,…,um,由于對稱性,只對vl和vi的位置進行討論。

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].華東師范大學學報(自然科學版),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),趙飚.固定直徑的樹的Harary指數(shù)[J].曲阜師范大學學報(自然科學版),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].長沙：湖南師范大學,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.

(責任編輯劉 舸)

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

國家自然科學基金資助項目(11301489)

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

伊佳茹，雷英杰.給定直徑的單圈圖的Harary指數(shù)[J].重慶理工大學學報(自然科學)，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