The Harary Index of Digraphs

Abstract

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph and named in honor of Professor Frank Harary. For a connected graph \(G = (V, E)\) with edge connectivity \(\lambda(G) \geq 2\), and an edge \(v_iv_j \in E(G)\), \(G – v_iv_j\) is the subgraph formed from \(G\) by deleting the edge \(v_iv_j\). Denote the Harary index of \(G\) and \(G – v_iv_j\) by \(H(G)\) and \(H(G – v_iv_j)\). Xu and Das [K.X. Xu, K.C. Das, On Harary index of graphs, Discrete Appl. Math. 159 (2011) 1631–1640] obtained lower and upper bounds on \(H(G + v_iv_j) – H(G)\) and characterized the equality cases in those bounds. We find that the equality case in the lower bound is not true and we correct it. In this paper, we give lower and upper bounds on \(H(G) – H(G – v_iv_j)\), and provide some graphs to satisfy the equality cases in these bounds. Furthermore, we extend the Harary index to directed graphs and obtain similar conclusions.