Minimum Wiener Index of Triangulations and Quadrangulations

2020/03/09 by Czabarka, Éva, Olsen, Trevor, Smith, Stephen +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2003.03873

Abstract

The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. We provide formulae for the minimum Wiener index of simple triangulations and quadrangulations with connectivity at least c, and provide the extremal structures, which attain those values. Our main tool is setting upper bounds for the maximum degree in highly connected triangulations and quadrangulations.

Related

• Wiener Index of Quadrangulation Graphs
• Selected topics on Wiener index
• Wiener index of graphs with fixed number of pendant or cut vertices
• An upper bound on the Wiener Index of a k-connected graph
• On vertex peripherians and Wiener index of graphs with fixed number of cut vertices