On connected graphs and trees with maximal inverse sum indeg index

摘要

Let G=(V,E) be a graph. The inverse sum indeg index (ISI index in short) of G is defined as ISI(G)=∑vivj∈Edidj/(di+dj), where di is the degree of vertex vi. This recently developed topological index can predict total surface area for octane isomers. It is known that the star Sn uniquely minimizes the ISI index among n-vertex trees. However, characterizing n-vertex tree(s) with maximal ISI index (optimal trees, for convenience) appears to be difficult. There are even no sound conjectures on their structure up to now.Let π be a degree sequence, and C(π) the set of connected graphs whose degree sequence is π. In the present paper, it is proven that, there exists a so-called BFS-graph that maximizes the ISI index in C(π). This enables us to conduct a computer search for n-vertex optimal tree(s) up to n=150. Based on the search outputs, some structural properties of an optimal tree are observed and proven. Finally, some problems and conjectures are proposed, which may indicate the directions for further work towards the complete characterization of optimal trees.