Geodesic
Identifying \(X\)-trees with few characters
The electronic journal of combinatorics, Tome 13 (2006)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
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).
DOI : 10.37236/1109
Classification : 92D15, 05C05 
Magnus Bordewich; Charles Semple; Mike Steel. Identifying \(X\)-trees with few characters. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1109
@article{10_37236_1109,
     author = {Magnus Bordewich and Charles Semple and Mike Steel},
     title = {Identifying {\(X\)-trees} with few characters},
     journal = {The electronic journal of combinatorics},
     year = {2006},
     volume = {13},
     doi = {10.37236/1109},
     zbl = {1106.92052},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1109/}
}
TY  - JOUR
AU  - Magnus Bordewich
AU  - Charles Semple
AU  - Mike Steel
TI  - Identifying \(X\)-trees with few characters
JO  - The electronic journal of combinatorics
PY  - 2006
VL  - 13
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1109/
DO  - 10.37236/1109
ID  - 10_37236_1109
ER  - 
%0 Journal Article
%A Magnus Bordewich
%A Charles Semple
%A Mike Steel
%T Identifying \(X\)-trees with few characters
%J The electronic journal of combinatorics
%D 2006
%V 13
%U http://geodesic.mathdoc.fr/articles/10.37236/1109/
%R 10.37236/1109
%F 10_37236_1109

Cité par Sources :