Identifying $X$-Trees with Few Characters

Abstract

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