The \(\text{Cay(G, S)}\)  of a transposition tree \(T\)  can be viewed as the state diagram of a permutation puzzle on \(T\) , where the vertices of \(\text{Cay(G, S)}\)  is the possible positions of markers on \(T\)  and each edge of \(\text{Cay(G, S)}\)  corresponds to a legal move of the permutation puzzle on \(T\) . An upper bound of the minimum number of legal moves to reach the final position \(Q\)  for a given initial position \(P\)  is indeed the diameter of \(\text{Cay(G, S)}\)  [1]} of a transposition tree \(T\) . Moreover, the inequality in Corollary REF  can be replaced by the equality for the cases of bubble sort and star graphs [2]}.
