Wiener Indices of Balanced Binary Trees

Sergey Bereg, Hao WangLecture Notes in Computer Science 2005 · DOI · OpenAlex

Introduction

The Wiener index, introduced by Harry Wiener in 1947, is a topological descriptor used in chemical graph theory to represent the structure of acyclic organic compounds. Mathematically, for a graph $G$, the Wiener index $W(G)$ is defined as the sum of distances between all pairs of vertices. A long-standing open question, the Wiener Index Conjecture, asks whether every positive integer can be the Wiener index of some tree.

While previous work suggested that most integers are covered, the trees used often featured vertices with high degrees, which are chemically unrealistic. In 2005, Sergey Bereg and Hao Wang investigated this conjecture by restricting the search to binary trees (maximum degree 3), which more closely resemble molecular structures like alkanes.

The $k$-tree Framework

To systematically explore binary trees, the authors introduced a hierarchy of balanced structures called $k$-trees:

  • 0-trees are perfectly complete binary trees.
  • 1-trees are nearly complete, where only the leaf nodes at the maximum depth may vary in number.
  • $k$-trees offer increasing flexibility as $k$ grows, allowing for a broader range of internal distances while maintaining a degree of balance.

Methodology: Tree Transformations and DP

The authors developed efficient algorithms to enumerate Wiener indices. They utilized recursive formulas to calculate $W(T)$ based on subtrees and derived exact formulas for tree transformations.

Tree transformations used to derive formulas for changes in the Wiener index.

By analyzing how the index changes when subtrees are swapped or joined (as shown above), they established properties that simplify computation. For example, in 1-trees, the sum of distances from the root to all other nodes is constant for a fixed size $n$. They implemented dynamic programming (DP) algorithms with complexities of $O(n^6 \log n)$ for 1-trees and $O(n^7 \log n)$ for general $k$-trees.

Density and Coverage

A key finding of the study is that the "density" of available Wiener indices increases significantly with the number of vertices $n$.

Density of Wiener indices as a function of tree size.

As shown in the density plot, the gaps between possible Wiener indices tend to disappear as the tree size grows. For 2-trees of size up to $n=90$, the authors found that every integer between 8,864 and 30,224 is achievable. This led to Conjecture 11: the set of Wiener indices for 2-trees contains all integers greater than 8,863.

Conclusion

The computational evidence provided by Bereg and Wang strongly supports the Wiener Index Conjecture within the realm of chemically realistic binary trees. Their work demonstrates that high-degree vertices are not necessary to cover the set of integers. While a formal proof for the entire set remains open, the polynomial-time algorithms and the observed density trends provide a robust foundation for future theoretical breakthroughs.

Summary updated

BibTeX
@inproceedings{bereg2005wiener,
  author = {Sergey Bereg and Hao Wang},
  title = {{Wiener Indices of Balanced Binary Trees}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2005},
  doi = {10.1007/11428848\_109},
}
Figure