Average distance and independence number (Q1329805): Difference between revisions

For a connected graph \(G\) of order \(n\), the average distance \(\mu(G)\) is defined as \[ \mu(G)= \left({n\atop 2}\right)^{-1} \sum_{u,v\in V(G)} d(u,v), \] where \(d(u,v)\) denotes the length of a shortest path joining the vertices \(u\) and \(v\). In this paper, the author gives a sharp upper bound on \(\mu(G)\) depending on the order and the independence number. The maximum average distance of a graph with given order and matching number is also obtained. All extremal graphs are determined.