Minimizing Wiener index for vertex-weighted trees with given weight and degree sequences. (English) Zbl 1461.05056
Summary: S. Klavžar and I. Gutman [Discrete Appl. Math. 80, No. 1, 73–81 (1997; Zbl 0889.05046)] 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.
MSC:
05C09 | Graphical indices (Wiener index, Zagreb index, Randić index, etc.) |
05C92 | Chemical graph theory |
92E10 | Molecular structure (graph-theoretic methods, methods of differential topology, etc.) |
05C12 | Distance in graphs |