Publication

Abstract : Let r be a Cayley graph generated by a transposition tree T on n vertices. In an oft-cited paper [1] (see also [9]), 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.