The Number of Shortest Paths in the
We enumerate all of the shortest paths between any vertex v and the identity vertex in an (n, k)-star graph by enumerating the minimum factorizations of v in terms of the transpositions corresponding to edges in that graph. This result generalizes a previous one for the star
graph, and can be applied to obtain the number of the shortest paths between a pair of vertices in some of the other similar
structures. It also implies an algorithm to enumerate all such paths.