The maximum Wiener index of maximal planar graphs

DOI10.1007/S10878-020-00655-4MaRDI QIDQ830949zbMATH OpenOpenAlexFDO

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

Publication date 10 May 2021

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1912.02846

zbMATH Keywords

distancemini-maxplanar graphstriangulationWiener index

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12) Extremal problems in graph theory (05C35)

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 $lfloorfrac118(n^3+3n^2)floor$. We prove this conjecture and for every $n$, $ngeq10$, determine the unique $n$-vertex maximal planar graph for which this maximum is attained.

Recommendations

• An upper bound on Wiener indices of maximal planar graphs
• On the two conjectures of the Wiener index
• Maximizing Wiener index of graphs with fixed maximum degree
• Ordering trees and connected graphs by their Wiener index
• Wiener index of quadrangulation graphs

Cites work

• A class of trees and its Wiener index
• A survey on graphs extremal with respect to distance-based topological indices
• All but 49 numbers are Wiener indices of trees
• An upper bound on Wiener indices of maximal planar graphs
• Average Distance and Edge-Connectivity I
• Average Distance and Edge-Connectivity II
• Average distance and vertex-connectivity
• Average distance, minimum degree, and spanning trees
• Distance in graphs
• Edge-vulnerability and mean distance
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 90560 (Why is no real title available?)
• Inverse problem on the Steiner Wiener index
• Mathematical aspects of Wiener index
• Mean distance and minimum degree
• Molecular graphs and the inverse Wiener index problem
• On maximum Wiener index of trees and graphs with given radius
• On the sum of all distances in a graph or digraph
• On Wiener index of common neighborhood graphs
• Using minimum degree to bound average distance
• Wiener index in weighted graphs via unification of \(\varTheta^\ast\)-classes
• Wiener index of Eulerian graphs
• Wiener index of hexagonal systems
• Wiener index of trees of given order and diameter at most 6
• Wiener index of trees: Theory and applications
• Wiener index versus maximum degree in trees

Cited in

(14)

• An upper bound on Wiener indices of maximal planar graphs
• Proof of a conjecture on the Wiener index of Eulerian graphs
• Minimum Wiener index of triangulations and quadrangulations
• A proof of a conjecture on maximum Wiener index of oriented ladder graphs
• Maximal Wiener index for graphs with prescribed number of blocks
• Wiener indices of maximal \(k\)-degenerate graphs
• On a ratio of Wiener indices for embedded graphs
• Proximity in triangulations and quadrangulations
• The Wiener index of maximal outerplane graphs
• Extremal by Wiener index maximal outerplane graphs with two simplicial vertices
• On the two conjectures of the Wiener index
• The maximum Wiener index of a uniform hypergraph
• The number of connected sets in Apollonian networks
• The maximum Wiener index of some oriented graphs

This page was built for publication: The maximum Wiener index of maximal planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q830949)