  The distribution of distances in the star graph $ST_n$, ($1<n\in\Z$), is
established, and subsequently a threaded binary tree is obtained that realizes
an orientation of $ST_n$ whose levels are given by the distances to the
identity permutation, via a pruning algorithm followed by a threading
algorithm. In the process, the distributions of distances of the efficient
dominating sets of $ST_n$ are determined.
