  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.
