Characterizing path-length matrices of unrooted binary trees

Catanzaro, Daniele;Pesenti, Raffaele;Ronco, Roberto
(2024) , 27 pages

Files

CORE_DP_2024-28.pdf
  • Open Access
  • Adobe PDF
  • 1.01 MB
Download

Details

Authors
Abstract
We extend some recent results on the necessary and sufficient conditions that a symmetric integer matrix of order n ≥3 must satisfy to encode the Path-Length Matrix (PLM) of a Unrooted Binary Tree (UBT) with n leaves. This problem is at the core of the combinatorics of the Balanced Minimum Evolution Problem, a NP-hard problem much studied in the literature on molecular phylogenetics. We show that, for any natural 3 ≤n ≤11, a reduced set of known conditions, excluding Buneman’ strong four-point conditions, is both necessary and sufficient to characterize PLMs of UBTs. In addition, we present a second and more general characterization based solely on linear conditions derived from the topological properties of UBTs.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Catanzaro, D., Pesenti, R., & Ronco, R. (2024). Characterizing path-length matrices of unrooted binary trees (LIDAM Discussion Paper CORE 2024/28). https://hdl.handle.net/2078.5/235627