Publication Type:

Journal Article

Authors:

Ganesan, A.

Source:

Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 84, p.29-40 (2013)

URL:

http://www.scopus.com/inward/record.url?eid=2-s2.0-84874873822&partnerID=40&md5=4dffe05526028c9bafa94db5f4b18fc9

Keywords:

Cayley graphs, Diameter, Functions, Interconnection networks, Permutation group, Permutations, Transposition trees, Trees (mathematics)

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.

Notes:

cited By (since 1996)0

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.

207
PROGRAMS
OFFERED
5
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
9th
RANK(INDIA):
NIRF 2017
150+
INTERNATIONAL
PARTNERS