Diameters of Cayley graphs generated by transposition trees

Let G=〈S〉G=〈S〉 be a group, and let ΓΓ be its Cayley graph. Computing the diameter of ΓΓ is a computationally hard problem which comes up in several contexts. Thus, it is useful to be able to compute bounds on the diameter of Cayley graphs. Ganesan [6] studied the case where SS is a minimal set of transpositions which generate GG, and provided an algorithm to find an upper bound on diamΓ without examining each permutation. Expanding on this work, we give several new algorithms to compute upper bounds on the diameter of ΓΓ, without examining individual elements of GG. In particular, we give one algorithm which is much faster to compute than Ganesan’s, and one which produces better bounds than previous algorithms.