## On the strictness of a bound for the diameter of Cayley graphs generated by transpositions trees

Publication Type : Conference Proceedings

Publisher : Proceedings of the International Conference on Mathematical Modelling Scientific Computation

Source : Proceedings of the International Conference on Mathematical Modelling & Scientific Computation, Springer - Verlag CCIS Serie, Volume 238, Gandhigram, p.54-61 (2012)

Keywords : Cayley graphs Transposition trees Permutation groups Diameter Interconnection networks

Campus : Coimbatore

School : School of Engineering

Department : Mathematics

Verified : Yes

Year : 2012

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: diam(Γ) ≤ maxπ∈Sn{c(π)−n+∑i=1ndistT(i,π(i))}, where the maximization is over all permutations π in the symmetric group, c(π) denotes the number of cycles in π, and distT 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 .

Cite this Research Publication : A. Ganesan, “On the strictness of a bound for the diameter of Cayley graphs generated y transpositions trees”, Proceedings of the International Conference on Mathematical Modelling & Scientific Computation, vol. 238. Springer - Verlag CCIS Serie, Gandhigram, pp. 54-61, 2012.