Bounding the diameter of cayley graphs generated by specific transposition trees

摘要

A transposition tree T can be defined over permutations where the positions within a permutation define the vertices of the tree and an edge (i, j) of T signifies that the symbols at the positions i and j can be swapped. A Cayley graph of a permutation group can be generated by a transposition tree T where the edges of T form the generator set. Identifying the diameter value of a Cayley graph helps is equivalent to determining the maximum possible latency of communication in the corresponding interconnection network where the latency is measured in terms of the number of hops. In general, computation of the diameter is intractable. Thus, determining an upper bound on the diameter value is sought. In particular, tighter upper bounds are keenly pursued. Several existing methods compute an upper bound on the diameter value. The first known method has exponential time complexity. Later on, several articles introduced polynomial time algorithms. This article compares various methods. Furthermore, exact diameters for novel classes of trees are identified.