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/co-author 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 fi rst few and last few entries of the STF-vector. 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 non-isomorphic pairs of unlabeled free (i.e.unrooted) trees that are STF-equivalent, i.e. have identical subtree frequency vectors. Using exhaustive computer search, we determine all such pairs for small sizes. We show that there are infi nitely many non-isomorphic STF-equivalent pairs of trees by constructing infi nite 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 Classi fication (2010): 05C05.
Keywords: Tree reconstruction, subtree size frequencies.
  
         
     
         
         
      Back to previous page