Identifying \(X\)-trees with few characters
type: Item
instance of: scholarly article
title: Identifying \(X\)-trees with few characters
zbMATH Open document ID: 1106.92052
author: Magnus Bordewich
author: Charles Semple
author: Mike Steel
published in: The Electronic Journal of Combinatorics
publication date: 2007-03-12T00:00:00Z
full work available at URL: https://eudml.org/doc/126960
full work available at URL: v13i1r83.html
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).
Mathematics Subject Classification ID: 92D15
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 5132796
MaRDI profile type: Publication
Recommended article: A characterization of \(k\)-trees
Recommended article: Bounds on the identifying codes in trees
Recommended article: Identifying codes in trees and planar graphs
Recommended article: Distinguishing trees in linear time
Recommended article: Q4856907
Recommended article: Counting and coding identity trees with fixed diameter and bounded degree
Recommended article: Minimal identifying codes in trees and planar graphs with large girth
Recommended article: On a Characterization of Trees
Recommended article: Q4659582
Recommended article: Sequences Characterizing k-Trees
description: scientific article; zbMATH DE number 5132796