Minimum triplet covers of binary phylogenetic X-trees

Huber, Katharina T., Moulton, Vincent ORCID: and Steel, Mike (2017) Minimum triplet covers of binary phylogenetic X-trees. Journal of Mathematical Biology, 75 (6-7). 1827–1840. ISSN 0303-6812

[thumbnail of art10.1007--00285-017-1117-6]
PDF (art10.1007--00285-017-1117-6) - Published Version
Available under License Creative Commons Attribution.

Download (541kB) | Preview


Trees with labelled leaves and with all other vertices of degree three play an important role in systematic biology and other areas of classification. A classical combinatorial result ensures that such trees can be uniquely reconstructed from the distances between the leaves (when the edges are given any strictly positive lengths). Moreover, a linear number of these pairwise distance values suffices to determine both the tree and its edge lengths. A natural set of pairs of leaves is provided by any `triplet cover' of the tree (based on the fact that each non-leaf vertex is the median vertex of three leaves). In this paper we describe a number of new results concerning triplet covers of minimum size. In particular, we characterize such covers in terms of an associated graph being a 2-tree. Also, we show that minimum triplet covers are `shellable' and thereby provide a set of pairs for which the inter-leaf distance values will uniquely determine the underlying tree and its associated branch lengths.

Item Type: Article
Additional Information: Open Access: This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Uncontrolled Keywords: trees,median vertex,2-trees,shellability,reconstruction
Faculty \ School: Faculty of Science > School of Computing Sciences
UEA Research Groups: Faculty of Science > Research Groups > Computational Biology
Faculty of Science > Research Groups > Norwich Epidemiology Centre
Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User: Pure Connector
Date Deposited: 08 Mar 2017 01:41
Last Modified: 19 Apr 2023 20:31
DOI: 10.1007/s00285-017-1117-6


Downloads per month over past year

Actions (login required)

View Item View Item