Minimizing Wiener Index for Vertex-Weighted Trees with Given Weight and Degree Sequences

2015/02/28 by Mikhail Goubko · 1 citation
Mathematics · #math.CO

paper · pdf

published as MATCH Commun. Math. Comput. Chem., Volume 75 (2016) number 1, pp. 3-27 · 2 figures

arxiv created 2015/06/02 · arxiv updated 2015/09/23

Abstract

In 1997 Klavžar and Gutman suggested a generalization of the Wiener index to vertex-weighted graphs. We minimize the Wiener index over the set of trees with the given vertex weights' and degrees' sequences and show an optimal tree to be the, so-called, Huffman tree built in a bottom-up manner by sequentially connecting vertices of the least weights.

Cited by

• Efficient generation of networks with minimal average shortest-path distance