Computer Science – Discrete Mathematics
Scientific paper
2012-02-27
Computer Science
Discrete Mathematics
A conference version that includes parts of arXiv:1111.3114
Scientific paper
A problem of much theoretical and practical interest is to determine or estimate the diameter of various families of Cayley graphs. Let $\Gamma$ be a Cayley graph on $n!$ vertices generated by a transposition tree on vertex set ${1,2,...,n}$. In an oft-cited paper \cite{Akers:Krishnamurthy:1989} (cf. also \cite[p. 188]{Hahn:Sabidussi:1997}), it is shown that the diameter of $\Gamma$ is bounded as $$\diam(\Gamma) \le \max_{\pi \in S_n}{c(\pi)-n+\sum_{i=1}^n \dist_T(i,\pi(i))},$$ where the maximum is over all permutations in $S_n$, $c(\pi)$ denotes the number of cycles in the disjoint cycle representation of $\pi$, and $\dist_T$ is the distance function on pairs of vertices of the tree. Observe that evaluating this upper bound requires $\Omega(n! n^2)$ computations since the quantity in braces above needs to be evaluated for each permutation in $S_n$. In this work, we describe an algorithm to estimate the diameter of the Cayley graph which requires far fewer computations, and furthermore, we show that the value computed by the proposed algorithm is at least as good as (i.e. is less than or equal to) the above upper bound, and that sometimes the value computed is strictly less than the above upper bound. This result is possible because our algorithm works directly with the transposition tree on $n$ vertices and does not require examining any of the permutations. We also show that the value computed by our algorithm is not necessarily unique. We briefly mention a number of new questions and open problems at the end.
No associations
LandOfFree
Diameter of Cayley graphs generated by transposition trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Diameter of Cayley graphs generated by transposition trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Diameter of Cayley graphs generated by transposition trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-263287