The maximum Wiener index of maximal planar graphs

Debarun Ghosh; Ervin Győri; Addisu Paulos; Nika Salia; Oscar Zamora

doi:10.1007/s10878-020-00655-4

The maximum Wiener index of maximal planar graphs

Debarun Ghosh, Ervin Győri, Addisu Paulos, Nika Salia^*, Oscar Zamora

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

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 ⌊118(n3+3n2)⌋. We prove this conjecture and determine the unique n-vertex maximal planar graph attaining this maximum, for every n≥ 10.

Original language	English
Pages (from-to)	1121-1135
Number of pages	15
Journal	Journal of Combinatorial Optimization
Volume	40
Issue number	4
DOIs	https://doi.org/10.1007/s10878-020-00655-4
State	Published - 1 Nov 2020
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2020, The Author(s).

Keywords

Distance
Mini–Max
Planar graphs
Triangulation
Wiener index

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-020-00655-4

Cite this

@article{5b63330d5d3441068e8edb97bc67afc0,

title = "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 ⌊118(n3+3n2)⌋. We prove this conjecture and determine the unique n-vertex maximal planar graph attaining this maximum, for every n≥ 10.",

keywords = "Distance, Mini–Max, Planar graphs, Triangulation, Wiener index",

author = "Debarun Ghosh and Ervin Gy{\H o}ri and Addisu Paulos and Nika Salia and Oscar Zamora",

note = "Publisher Copyright: {\textcopyright} 2020, The Author(s).",

year = "2020",

month = nov,

day = "1",

doi = "10.1007/s10878-020-00655-4",

language = "English",

volume = "40",

pages = "1121--1135",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - The maximum Wiener index of maximal planar graphs

AU - Ghosh, Debarun

AU - Győri, Ervin

AU - Paulos, Addisu

AU - Salia, Nika

AU - Zamora, Oscar

PY - 2020/11/1

Y1 - 2020/11/1

N2 - 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 ⌊118(n3+3n2)⌋. We prove this conjecture and determine the unique n-vertex maximal planar graph attaining this maximum, for every n≥ 10.

AB - 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 ⌊118(n3+3n2)⌋. We prove this conjecture and determine the unique n-vertex maximal planar graph attaining this maximum, for every n≥ 10.

KW - Distance

KW - Mini–Max

KW - Planar graphs

KW - Triangulation

KW - Wiener index

UR - http://www.scopus.com/inward/record.url?scp=85091951221&partnerID=8YFLogxK

U2 - 10.1007/s10878-020-00655-4

DO - 10.1007/s10878-020-00655-4

M3 - Article

AN - SCOPUS:85091951221

SN - 1382-6905

VL - 40

SP - 1121

EP - 1135

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

The maximum Wiener index of maximal planar graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this