The number of shortest paths in the arrangement graph.

Abstract: A solution to the shortest path enumeration problem can find numerous applications in studying issues related to interconnection networks. In this paper, we enumerate the number of shortest paths between any two vertices in an arrangement graph by establishing a bijection between these shortest paths and a collection of ordered forests of certain bi-colored trees, via minimum factorizations of permutations corresponding to such vertices in terms of so-called arrangement transpositions, and then count the number of these forests with the help of an existing result on the enumeration of such bi-colored trees. Our result generalizes previous ones and can be applied to solve the same problem for other related graphs such as the alternating group graph. On the other hand, the techniques applied to derive such an enumeration result further extend the ongoing work of counting the number of minimum factorizations of a permutation in terms of a certain type of transposition, a rather interesting problem in the area of algebraic combinatorics. [Copyright &y& Elsevier]