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).

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 ??
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 ??