Skip to main content
main-content

Tipp

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

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 4/2020
Autoren:
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.

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

Weitere Artikel der Ausgabe 4/2020

Journal of Combinatorial Optimization 4/2020 Zur Ausgabe

Premium Partner

    Bildnachweise