The set of all permutations with $n$ symbols is a symmetric group denoted by $S_n$. A transposition tree, $T$, is a spanning tree over its $n$ vertices $V_T=${$1, 2, 3, \ldots n$} where the vertices are the positions of a permutation $\pi$ and $\pi$ is in $S_n$. $T$ is the operation and the edge set $E_T$ denotes the corresponding generator set. The goal is to sort a given permutation $\pi$ with $T$. The number of generators of $E_T$ that suffices to sort any $\pi \in S_n$ constitutes an upper bound. It is an upper bound, on the diameter of the corresponding Cayley graph $\Gamma$ i.e. $diam(\Gamma)$. A precise upper bound equals $diam(\Gamma)$. Such bounds are known only for a few trees. Jerrum showed that computing $diam(\Gamma)$ is intractable in general if the number of generators is two or more whereas $T$ has $n-1$ generators. For several operations computing a tight upper bound is of theoretical interest. Such bounds have applications in evolutionary biology to compute the evolutionary relatedness of species and parallel/distributed computing for latency estimation. The earliest algorithm computed an upper bound $f(\Gamma)$ in a $\Omega(n!)$ time by examining all $\pi$ in $S_n$. Subsequently, polynomial time algorithms were designed to compute upper bounds or their estimates. We design an upper bound $\delta^*$ whose cumulative value for all trees of a given size $n$ is shown to be the tightest for $n \leq 15$. We show that $\delta^*$ is tightest known upper bound for full binary trees. Keywords: Transposition trees, Cayley graphs, permutations, sorting, upper bound, diameter, greedy algorithms.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok