The maximum Wiener index of maximal planar graphs

被引：7

作者：

Ghosh, Debarun ^{[1
]}

Gyori, Ervin ^{[1
,2
]}

Paulos, Addisu ^{[1
,3
]}

Salia, Nika ^{[1
,2
]}

Zamora, Oscar ^{[1
,4
]}

机构：

[1] Cent European Univ, Budapest, Hungary

[2] Alfred Renyi Inst Math, Budapest, Hungary

[3] Addis Ababa Univ, Addis Ababa, Ethiopia

[4] Univ Costa Rica, San Jose, Costa Rica

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2020年 / 40卷 / 04期

基金：

美国国家科学基金会;

关键词：

Wiener index; Planar graphs; Triangulation; Distance; Mini-Max; AVERAGE DISTANCE; MINIMUM DEGREE; TREES;

D O I：

10.1007/s10878-020-00655-4

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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 theWiener index of an n-vertex maximal planar graph is at most left perpendicular1/18 (n(3) + 3n(2))right perpendicular. We prove this conjecture and determine the unique n-vertex maximal planar graph attaining this maximum, for every n >= 10.

引用

页码：1121 / 1135

页数：15

共 32 条

[1] Using minimum degree to bound average distance [J].