Additively weighted Harary index of some composite graphs (Q1759808)

The paper under review introduces a modification of the Harary index of a connected graph. The Harary index of a connected graph \(G=(V,E)\) is \[ H(G)=\sum_{\{u,v\}\in V^{[2]}}\frac{1}{d(u,v)} \] where \(d(u,v)\) denotes the graph distance between the two vertices \(u\neq v\in V\). Such indices are sometimes applied in chemistry. For example, the Harary index of a single edge is 1. The aim of the new invariant is to give extra weight to vertices with large degree. Specifically, the paper studies the additively weighted Harary index \[ H_{A}(G)=\sum _{\{u,v\}\in V^{[2]}}\frac{d(u)+d(v)}{d(u,v)}. \] Here \(d(w)\) is the degree of the vertex \(w\). Thus, letting \(K_{n}\) and \(S_{n}\) denote respectively a complete graph and a star on \(n\) vertices, \(H_{A}(K_{n})=n(n-1)^{2}\) and \(H_{A}(S_{n})=(n-1)(5n-2)/4\). It is clear that adding an edge can only increase \(H_{A}\), so the value for the complete graph is the maximum attainable: similarly a tree must have the smallest value. The authors use transformations on trees to show that amongst trees on \(n\) vertices, the path has the smallest \(H_{A}\) and the star the largest. They then discuss various ``composite graphs'', i.e. graphs obtained by putting two other graphs together in some way. They obtain various formulae for the additively weighted Harary indices of various graphs in terms of additively weighted Harary indices of the two input graphs and the so-called Zagreb indices of the graphs. Some future directions for research are also indicated.