Back close

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

Publication Type : Journal Article

Publisher : Communications in Computer and Information Science

Source : Communications in Computer and Information Science, Volume 283 CCIS, Number 1, Gandhigram, Tamil Nadu, p.54-61 (2012)

Url :

ISBN : 9783642289255

Keywords : Cayley graphs, Diameter, Distance functions, Fault tolerance, Forestry, Graphic methods, Interconnection networks, Low diameters, Lower bounds, Mathematical models, Networks, Number of cycles, Open problems, Optimal fault tolerances, Permutation group, Symmetric groups, Transposition trees, Trees (mathematics), Upper Bound, Vertex set, Worst-case performance

Campus : Coimbatore

School : School of Engineering

Department : Mathematics

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: (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.

Cite this Research Publication : A. Ganesan, “On the strictness of a bound for the diameter of Cayley graphs generated by transposition trees”, Communications in Computer and Information Science, vol. 283 CCIS, pp. 54-61, 2012.

Admissions Apply Now