Combinatorial properties of triplet covers for binary trees

DOI10.1016/J.AAM.2018.04.002MaRDI QIDQ1637594zbMATH OpenOpenAlexFDO

Authors Stefan Grünewald, Katharina T. Huber, Vincent Moulton, Mike Steel

Publication date 8 June 2018

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.07908, https://ueaeprints.uea.ac.uk/id/eprint/66773/1/triplet_cover_elsearticle_2018_04_10.pdf

zbMATH Keywords

ample patchworkHall's theoremphylogenetic treeshellabilitytree-distancestriplet cover

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problems related to evolution (92D15)

Abstract: It is a classical result that an unrooted tree $T$ having positive real-valued edge lengths and no vertices of degree two can be reconstructed from the induced distance between each pair of leaves. Moreover, if each non-leaf vertex of $T$ has degree 3 then the number of distance values required is linear in the number of leaves. A canonical candidate for such a set of pairs of leaves in $T$ is the following: for each non-leaf vertex $v$, choose a leaf in each of the three components of $T-v$, group these three leaves into three pairs, and take the union of this set over all choices of $v$. This forms a so-called 'triplet cover' for $T$. In the first part of this paper we answer an open question (from 2012) by showing that the induced leaf-to-leaf distances for any triplet cover for $T$ uniquely determine $T$ and its edge lengths. We then investigate the finer combinatorial properties of triplet covers. In particular, we describe the structure of triplet covers that satisfy one or more of the following properties of being minimal, 'sparse', and 'shellable'.

Recommendations

• Minimum triplet covers of binary phylogenetic \(X\)-trees
• Combinatorial proof of the Prodinger formulas about binary trees
• scientific article; zbMATH DE number 2221988
• Combinatorics of non-ambiguous trees
• Combinatorics of non-ambiguous trees
• scientific article; zbMATH DE number 2232270
• On the tree cover number of a graph
• Nontrivial convex covers of trees

Cites work

• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers
• A Hall-type theorem for triplet set systems based on medians in trees
• A matroid associated with a phylogenetic tree
• Minimum triplet covers of binary phylogenetic \(X\)-trees
• On some relations between 2-trees and tree metrics
• On the extension of a partial metric to a tree metric
• Patchworks
• Tree reconstruction from triplet cover distances

Cited in

(3)

• Minimum triplet covers of binary phylogenetic \(X\)-trees
• Phylogenetic flexibility via Hall-type inequalities and submodularity
• Tree reconstruction from triplet cover distances

This page was built for publication: Combinatorial properties of triplet covers for binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1637594)