Identifying X-Trees with Few Characters

Bordewich, M.; Semple, C.; Steel, M.A.

Abstract

Previous work has shown the perhaps surprising result that, for any binary phylogenetic tree T, there is a set of four characters that define T. Here we deal with the general case, where T is an arbitrary X-tree. We show that if d is the maximum degree of any vertex in T, then the minimum number of characters that identify T is log2d (up to a small multiplicative constant).

Citation

Bordewich, M., Semple, C., & Steel, M. (2006). Identifying X-Trees with Few Characters. Electronic Journal of Combinatorics, 13(1),

• Journal Article Type: Article
• Publication Date: Sep 28, 2006
• Deposit Date: Jan 5, 2010
• Publicly Available Date: Jan 6, 2010
• Journal: Electronic Journal of Combinatorics
• Publisher: Electronic Journal of Combinatorics
• Peer Reviewed: Peer Reviewed
• Volume: 13
• Issue: 1
• Public URL: https://durham-repository.worktribe.com/output/1522690
• Publisher URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r83