Mathematicians Solve 41-Year Tree Theory Problem With Real-World Applications
Researchers have finally proved a decades-old conjecture about how networks shrink when connections are removed—a finding with implications for optimizing everything from supply chains to telecommunications infrastructure. The proof resolves a question that's been open since 1983 and could improve algorithms used to analyze complex systems.
Originaltitel: On the difference of mean subtree orders under edge contraction
<p>Given a tree T of order n , one can contract any edge and obtain a new tree T & lowast; of order n - 1. In 1983, Jamison made a conjecture that the mean subtree order, i.e., the average order of all subtrees, decreases at least 31 in contracting an edge of a tree. In 2023, Luo, Xu, Wagner and Wang proved the case when the edge to be contracted is a pendant edge. In this article, we prove that the conjecture is true in general. (c) 2024 The Author. Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons.org/licenses/by/4.0/).</p>