
On Cayley Graphs on the Symmetric Group Generated by Tranpositions
 Postscript version.
 Dvi version.
 PDF version.

Abstract:
Given a connected graph, $X$, we denote by $\lambda_2=\lambda_2(X)$ its
smallest
nonzero Laplacian eigenvalue.
In this paper we show that among all sets of $n1$ transpositions which
generate the symmetric group, $S_n$, the set whose associated Cayley graph
has the highest $\lambda_2$ is the set $\{(1,n),(2,n),\ldots,(n1,n)\}$ (or
the same with $n$ and $i$ exchanged for any $i
