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 non-zero Laplacian eigenvalue. In this paper we show that among all sets of $n-1$ 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,(n-1,n)\}$ (or the same with $n$ and $i$ exchanged for any $i