MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 added 44 characters in body

Consider the graph $G_n$, with $V(G_n) = S_n$ (the set of permutations of a set of size $n$) and having an edge $\sigma\sigma'$ iif $\sigma'$ can be obtained from $\sigma$ by applying a transposition.

This $G_n$, defined that way, has a "name"?

It seems pretty easy, (and this is the main question) but I'm not sure how $G_n$ "looks like". For instante:

  • $G_1$ is $K_1$
  • $G_2$ is $K_2$
  • $G_3$ is $K_{3,3}$
  • $G_4$ is ??
  • $\dots$
  • $G_n$ is ??
show/hide this revision's text 1

Graph of $S_n$ with respect to transposition

Consider the graph $G_n$, with $V(G_n) = S_n$ (the set of permutations of a set of size $n$) and having an edge $\sigma\sigma'$ iif $\sigma'$ can be obtained from $\sigma$ by applying a transposition.

This $G_n$, defined that way, has a "name"?

It seems pretty easy, but I'm not sure how $G_n$ "looks like". For instante:

  • $G_1$ is $K_1$
  • $G_2$ is $K_2$
  • $G_3$ is $K_{3,3}$
  • $G_4$ is ??
  • $\dots$
  • $G_n$ is ??