Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

03.10.2020 | Ausgabe 4/2020 Open Access

Journal of Combinatorial Optimization 4/2020

The maximum Wiener index of maximal planar graphs

Journal of Combinatorial Optimization > Ausgabe 4/2020
Debarun Ghosh, Ervin Győri, Addisu Paulos, Nika Salia, Oscar Zamora
Wichtige Hinweise

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


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 determine the unique n-vertex maximal planar graph attaining this maximum, for every \( n\ge 10\).
Über diesen Artikel

Weitere Artikel der Ausgabe 4/2020

Journal of Combinatorial Optimization 4/2020 Zur Ausgabe

Premium Partner