ProgramsView all programs
From the news
- Chancellor Amma Addresses the Parliament of World’s Religions
- Amrita Students Qualify for the European Mars Rover Challenge
Publication Type : Journal Article
Publisher : Journal of Combinatorial Mathematics and Combinatorial Computing
Source : Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 84, p.29-40 (2013)
Keywords : Cayley graphs, Diameter, Functions, Interconnection networks, Permutation group, Permutations, Transposition trees, Trees (mathematics)
Campus : Coimbatore
School : School of Engineering
Department : Mathematics
Verified : Yes
Year : 2013
Abstract : Let r be a Cayley graph generated by a transposition tree T on n vertices. In an oft-cited paper  (see also ), it was shown that the diameter of the Cayley graph T on n! vertices is bounded as (Mathematical formula presented) where the maximization is over all permutations π, in Snc(π) denotes the number of cycles in π, and distr is the distance function in T. It is of interest to determine for which families of trees this inequality holds with equality. In this work, we first investigate the sharpness of this upper bound. We prove that the above inequality is sharp for all trees of maximum diameter (i.e. all paths) and for all trees of minimum diameter (i.e. all stars), but the bound can still be strict for trees that are non-extremal. We also show that a previously known inequality on the distance between vertices in some families of Cayley graphs holds with equality and we prove that for some families of graphs an algorithm related to these bounds is optimal.
Cite this Research Publication : A. Ganesan, “On the sharpness of a bound on the diameter of Cayley graphs generated by transposition trees”, Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 84, pp. 29-40, 2013.