The Maximum Wiener Index of Maximal Planar Graphs

Abstract

The Wiener index of a connected graph is the sum of the distances between all pairs of vertices in the graph. It was conjectured that the Wiener index of an $n$-vertex maximal planar graph is at most $\lfloor \frac{1}{18}(n^3+3n^2)\rfloor$. We prove this conjecture and for every $n$, $n\ge 10$, determine the unique $n$-vertex maximal planar graph for which this maximum is attained.

13 pages, 4 figures