Star Graphs: Threaded Distance Trees and E-Sets

Abstract

The distribution of distances in the star graph $S{T}_n$ ($1<n\in \mathbb{Z}$) is established, and subsequently a threaded binary tree is obtained that realizes an orientation of $S{T}_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 $S{T}_n$ are determined.