Publication

Abstract : Cayley graphs have been well-studied as a model for interconnection networks due to their low diameter, optimal fault tolerance, and algorithmic efficiency, among other properties. A problem of practical and theoretical interest is to determine or estimate the diameter of Cayley graphs. Let Γ be a Cayley graph on n! vertices generated by a transposition tree on vertex set {1,2,...,n}. In an oft-cited paper [1], it was shown that the diameter of Γ is bounded as: (Equation Presented) where the maximization is over all permutations π in the symmetric group, c(π) denotes the number of cycles in π, and is the distance function in T. It is of interest to determine how far away this upper bound can be from the true diameter value in the worst case and for which families of graphs this bound should be utilized or not utilized. In this work, we investigate the worst case performance of this upper bound. We show that for every n, there exists a transposition tree on n vertices such that the maximum possible difference Δ n between the upper bound and the true diameter value is at least n - 4. The lower bound we provide for Δ n is seen to be best possible, and an open problem is to determine an upper bound for Δ n. © 2012 Springer-Verlag.