Topological classification of binary trees using the Horton-Strahler index

Area of Science:

• Combinatorics and Graph Theory
• Computational Biology
• Geophysics
• Computer Science

Background:

• The Horton-Strahler (HS) index is a significant metric with applications spanning physics, geology, biology, and computer science.
• Previous work established the HS index's relevance in diverse areas like river networks, pulmonary arteries, and register allocation.
• Enumeration problems for tree structures are fundamental in combinatorics and algorithm analysis.

Purpose of the Study:

• To revisit and provide an alternative derivation for the enumeration of the HS index on rooted, unlabeled, plane binary trees.
• To enumerate the HS index for the ambilateral set of rooted, plane binary trees with n leaves.
• To develop new analytical techniques for counting complex tree structures.

Main Methods:

• Developed an alternate derivation for the exact solution of HS index enumeration on unlabeled trees.
• Extended combinatorial techniques to address the ambilateral set of trees.
• Utilized a system of nonlinear functional equations to model the ambilateral tree set.

Main Results:

• Provided an alternative derivation for the existing exact solution for unlabeled trees.
• Derived a double exponentially converging approximant for generating functions of ambilateral trees.
• Obtained an explicit asymptotic form for the number of ambilateral trees.

Conclusions:

• The study successfully enumerates the Horton-Strahler index for both unlabeled and ambilateral plane binary trees.
• The developed methods offer efficient approximation and asymptotic analysis for complex tree structures.
• Findings contribute to a deeper understanding of combinatorial properties of trees and their applications.