Diameter and inverse degree (Q2470432): Difference between revisions

Let \(G\) be a connected graph on \(n\) vertices and with minimum degree \(\delta\). The average distance \(\mu(G)\) of \(G\) is defined as the average of the distances between all unordered pairs of vertices of \(G\). The inverse degree \(r(G)\) is defined as the sum of the inverses of the degrees of the vertices of \(G\). This paper is motivated by the GRAFFITI conjecture that \(\mu(G)\leq r(G)\). \textit{P. Erdős, J. Pach} and \textit{J. Spencer} [Congr. Numer. 64, 121--124 (1998; Zbl 0677.05053)] disproved the conjecture by constructing an infinite class of graphs with average distance at least \((\frac{2}{3}\lfloor \frac{r(G)}{3}\rfloor + \text{o}(1))\frac{\log n}{\log\log n}\). They also proved that \((6r(G) + 2+ \text (o)(1))\frac{\log n}{\log\log n}\) is an upper bound on the diameter of \(G\) which is therefore also an upper bound on the average distance since \(\mu(G)\) is at most equal to the diameter of \(G\). In this paper the authors improve this upper bound by a factor of two showing that the diameter of \(G\) (and hence \(\mu(G)\)) is at most equal to \((3r(G) + 2+ \text (o)(1))\frac{\log n}{\log\log n}\).