Skip to main content Skip to article
to view subscribed content from home

Discrete Applied Mathematics

Volume 159, Issue 15, 6 September 2011, Pages 1631-1640

On Harary index of graphs

Under an Elsevier
open archive


The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph G=(V,E) and two nonadjacent vertices vi and vj in V(G) of G, recall that G+vivj is the supergraph formed from G by adding an edge between vertices vi and vj. Denote the Harary index of G and G+vivj by H(G) and H(G+vivj), respectively. We obtain lower and upper bounds on H(G+vivj)H(G), and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained.


► We examine the changes of the Harary index of graphs when an edge is added. ► We obtain the extremal graphs w.r.t. the Harary index when clique number is given. ► We obtain the extremal graphs w.r.t. the Harary index when chromatic number is given.


Harary index
Clique number
Chromatic number

The first author is supported by NUAA Research Founding, No. NS2010205, the second author is supported by BK21 Math Modeling HRD Div. Sungkyunkwan University, Suwon, Republic of Korea.

View Abstract
<",c,' onload="var d=',n,";d.getElementsByTagName('head')[0].",d,"(d.",g,"('script')).",i,"='",a.l,"'\">"].join("")}var c="body",e=h[c];if(!e)return setTimeout(q,100);a.P(1);var d="appendChild",g="createElement",i="src",k=h[g]("div"),l=k[d](h[g]("div")),f=h[g]("iframe"),n="document",p;k.style.display="none";e.insertBefore(k,e.firstChild).id=o+"-"+j;f.frameBorder="0";f.id=o+"-frame-"+j;/MSIE[ ]+6/.test(navigator.userAgent)&&(f[i]="javascript:false");f.allowTransparency="true";l[d](f);try{f.contentWindow[n].open()}catch(s){a.domain=h.domain,p="javascript:var d="+n+".open();d.domain='"+h.domain+"';",f[i]=p+"void(0);"}try{var r=f.contentWindow[n];r.write(b());r.close()}catch(t){f[i]=p+'d.write("'+b().replace(/"/g,String.fromCharCode(92)+'"')+'");d.close();'}a.P(2)};a.l&&setTimeout(q,0)})()}();c[b].lv="1";return c[b]}var o="lightningjs",k=window[o]=g(o);k.require=g;k.modules=c}({}); window.usabilla_live = lightningjs.require("usabilla_live", "http://w.usabilla.com/eb1c14a91932.js"); var customData = {}; if(window.pageData && pageData.content && pageData.content[0]) { customData.entitlementType = pageData.content[0].entitlementType; } if(window.pageData && pageData.visitor) { customData.accessType = pageData.visitor.accessType; customData.accountId = pageData.visitor.accountId; customData.loginStatus = pageData.visitor.loginStatus; } usabilla_live("data", {"custom": customData });