Rezumat articol ediţie STUDIA UNIVERSITATIS BABE┼×-BOLYAI

În partea de jos este prezentat rezumatul articolului selectat. Pentru revenire la cuprinsul ediţiei din care face parte acest articol, se accesează linkul din titlu. Pentru vizualizarea tuturor articolelor din arhivă la care este autor/coautor unul din autorii de mai jos, se accesează linkul din numele autorului.

 
       
         
    STUDIA MATHEMATICA - Ediţia nr.4 din 2014  
         
  Articol:   RECONSTRUCTIBILITY OF TREES FROM SUBTREE SIZE FREQUENCIES.

Autori:  .
 
       
         
  Rezumat:   Let T be a tree on n vertices. The subtree frequency vector (STFvector) of  T, denoted by stf(T) is a vector of lengthwhose 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.
 
         
     
         
         
      Revenire la pagina precedentă