Exact Counts of Binary Phylogenetic Networks with Four Reticulations
Abstract
Phylogenetic networks provide a flexible framework for representing reticulate evolutionary processes, such as hybridization, introgression, recombination, and horizontal gene transfer. However, their combinatorial complexity makes even basic enumeration problems difficult. Building on our previous work for networks with up to three reticulations, we derive an explicit closed-form formula for the number of unrestricted rooted binary phylogenetic networks with four reticulations on n labeled taxa. Our approach is based on tree-component graphs. We classify the 79 possible component graphs corresponding to networks with four reticulations into ten groups. We then enumerate the networks associated with each group by combining known counts of one-component networks, forests, and networks with fewer reticulations. Summing these contributions yields the desired formula. This result extends the exact enumeration of unrestricted binary phylogenetic networks to four reticulations and further demonstrates the effectiveness of component graphs for systematically organizing and counting increasingly complex network classes.
Related
- Exact and asymptotic enumeration of unrestricted binary phylogenetic networks through automorphism weights
- The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks
- The parental parsimony problem on binary, tree-child phylogenetic networks
- Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy
- Best Matches in Phylogenetic Networks
BibTeX
@misc{yu2026exact,
title = {{Exact Counts of Binary Phylogenetic Networks with Four Reticulations}},
author = {Hao Yu and Louxin Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.21772},
eprint = {2609.21772},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21772},
}
RIS
TY - UNPB
TI - Exact Counts of Binary Phylogenetic Networks with Four Reticulations
AU - Hao Yu
AU - Louxin Zhang
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.21772
UR - https://arxiv.org/abs/2609.21772
AB - Phylogenetic networks provide a flexible framework for representing reticulate evolutionary processes, such as hybridization, introgression, recombination, and horizontal gene transfer. However, their combinatorial complexity makes even basic enumeration problems difficult. Building on our previous work for networks with up to three reticulations, we derive an explicit closed-form formula for the number of unrestricted rooted binary phylogenetic networks with four reticulations on n labeled taxa. Our approach is based on tree-component graphs. We classify the 79 possible component graphs corresponding to networks with four reticulations into ten groups. We then enumerate the networks associated with each group by combining known counts of one-component networks, forests, and networks with fewer reticulations. Summing these contributions yields the desired formula. This result extends the exact enumeration of unrestricted binary phylogenetic networks to four reticulations and further demonstrates the effectiveness of component graphs for systematically organizing and counting increasingly complex network classes.
ER -