On the ordering of distance-based invariants of graphs

摘要

Let d(u, v) be the distance between u and v of graph G, and let Wf(G) be the sum of f(d(u, v)) over all unordered pairs {u, v} of vertices of G, where f(x) is a function of x. In some literatures, Wf(G) is also called the Q-index of G. In this paper, some unified properties to Q-indices are given, and the majorization theorem is illustrated to be a good tool to deal with the ordering problem of Q-index among trees with n vertices. With the application of our new results, we determine the four largest and three smallest (resp. four smallest and three largest) Q-indices of trees with n vertices for strictly decreasing (resp. increasing) nonnegative function f(x), and we also identify the twelve largest (resp. eighteen smallest) Harary indices of trees of order n ≥ 22 (resp. n ≥ 38) and the ten smallest hyper-Wiener indices of trees of order n ≥ 18, which improve the corresponding main results of Xu (2012) and Liu and Liu (2010), respectively. Furthermore, we obtain some new relations involving Wiener index, hyper-Wiener index and Harary index, which gives partial answers to some problems raised in Xu (2012).