Identifying X-Trees with Few Characters

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

Identifying X-Trees with Few Characters

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

Authors

Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor

C. Semple

M.A. Steel

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
Publisher URL	http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r83