Sorting permutations with a transposition tree

Transforming permutations with several operations has been extensively studied where a transposition tree is one such operation. Such transformations have applications in genetics and interconnection networks. In genomic studies, a permutation models a genome. Likewise, in computer interconnection networks it denotes a node. A transposition tree T=(VT,ET) is a spanning tree over its vertices. In literature, Sn denotes the symmetric group formed by n symbols. A move of T on a permutation π ∈ Sn corresponds to any of e ∈ ET. If e=(i,j) then applying e to π swaps the symbols in positions i and j. The number of moves that suffice to sort any permutation in Sn with a given T is a upper bound for T. A precise upper bound equals the diameter of the corresponding Cayley graph Γ, i.e. diam (Γ). Jerrum showed that, in general, it is intractable to compute the diameter if the number of generators is at least two. Thus, computing a tighter upper bounds is of both theoretical ad practical interest. We compute a measure δ* that is an upper bound. The cumulative value of δ* for all trees with up to 15 vertices is the tightest known value. We define a class of trees called balanced-starburst; (k > 2) and show that δ* yields an upper bound for any tree in this class compated to the corresponding value of δ
^'
.