Identifying X-trees with few characters

MaRDI QIDQ869997zbMATH OpenFDO

Authors Magnus Bordewich, Charles Semple, Mike Steel

Publication date 12 March 2007

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/126960, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r83.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15)

Review text

Summary: Previous work has shown the perhaps surprising result that, for any binary phylogenetic tree \(T\), there is a set of four characters that defines \(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 \(\log_2 d\) (up to a small multiplicative constant).

Recommendations

• A characterization of \(k\)-trees
• Bounds on the identifying codes in trees
• Identifying codes in trees and planar graphs
• Distinguishing trees in linear time
• scientific article; zbMATH DE number 823452
• Counting and coding identity trees with fixed diameter and bounded degree
• Minimal identifying codes in trees and planar graphs with large girth
• On a Characterization of Trees
• scientific article; zbMATH DE number 2147927
• Sequences Characterizing k-Trees

Cited in

(5)

• Sharp upper and lower bounds on a restricted class of convex characters
• Defining a phylogenetic tree with the minimum number of r-state characters
• Phylogenetic trees defined by at most three characters
• On the information content of discrete phylogenetic characters
• Can you tell a tree from its branches?

This page was built for publication: Identifying \(X\)-trees with few characters

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