AMBIENTUM BIOETHICA BIOLOGIA CHEMIA DIGITALIA DRAMATICA EDUCATIO ARTIS GYMNAST. ENGINEERING EPHEMERIDES EUROPAEA GEOGRAPHIA GEOLOGIA HISTORIA HISTORIA ARTIUM INFORMATICA IURISPRUDENTIA MATHEMATICA MUSICA NEGOTIA OECONOMICA PHILOLOGIA PHILOSOPHIA PHYSICA POLITICA PSYCHOLOGIAPAEDAGOGIA SOCIOLOGIA THEOLOGIA CATHOLICA THEOLOGIA CATHOLICA LATIN THEOLOGIA GR.CATH. VARAD THEOLOGIA ORTHODOXA THEOLOGIA REF. TRANSYLVAN


The STUDIA UNIVERSITATIS BABEŞBOLYAI issue article summary The summary of the selected article appears at the bottom of the page. In order to get back to the contents of the issue this article belongs to you have to access the link from the title. In order to see all the articles of the archive which have as author/coauthor one of the authors mentioned below, you have to access the link from the author's name. 

STUDIA MATHEMATICA  Issue no. 4 / 2014  
Article: 
RECONSTRUCTIBILITY OF TREES FROM SUBTREE SIZE FREQUENCIES. Authors: . 

Abstract:
Let T be a tree on n vertices. The subtree frequency vector (STFvector) of T, denoted by stf(T) is a vector of length n whose kth coordinate is thenumber of subtrees of T that have exactly k vertices. We present algorithms for calculating the subtree frequencies.We give a combinatorial interpretation for the first few and last few entries of the STFvector. The main question we investigate  originally motivated by the problem of determining molecule structure from mass spectrometry data  is whether T can be reconstructed from stf(T). We show that there exist examples of nonisomorphic pairs of unlabeled free (i.e.unrooted) trees that are STFequivalent, i.e. have identical subtree frequency vectors. Using exhaustive computer search, we determine all such pairs for small sizes. We show that there are infinitely many nonisomorphic STFequivalent pairs of trees by constructing infinite families of examples. We also show that for special kinds of trees (e.g. paths, stars and trees containing a single vertex of degree larger than 2), the tree is reconstructible from the subtree frequencies. We consider a version of the problem for rooted trees, where only subtrees containing the root are counted. Finally, we formulate some conjectures and open problems and outline further research directions. Mathematics Subject Classification (2010): 05C05. Keywords: Tree reconstruction, subtree size frequencies. 
