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 deleted 153 characters in body; added 1 characters in body; added 107 characters in body

I claim the answer to your questin question is yes. This is my first time posting on mathoverflow. I hope my latex goes ok.

Given $\Gamma(S_n,A)$, build an auxiliary graph $X(\Gamma(S_n,A))$, with vertex set ${1,\ldots,n}$ and two vertices are adjacent if the corresponding involution is in $A$. Build a second auxiliary graph $Y$ with vertex set the elements of $A$ with an edge between them if they commute. Note that $Y$ is the complement of the line graph of $X$.

Let $\Gamma_1=\Gamma(S_n,A)$ and let $\Gamma_2=\Gamma(S_n,B)$.

We have to show that if $\Gamma_1$ and $\Gamma_2$ are isomorphic, then so are $X(\Gamma_1)$ and $X(\Gamma_2)$. By standard results on line graphs, Since $X(\Gamma_1)$ and $X(\Gamma_2)$ are connected, they are isomorphic if and only if $Y(\Gamma_1)$ and $Y(\Gamma_2)$ are (assuming they have at least 4 vertices, see http://en.wikipedia.org/wiki/Line_graph#Characterization_and_recognition). It thus suffices to show that if $\Gamma_1$ and $\Gamma_2$ are isomorphic, then so are $Y(\Gamma_1)$ and $Y(\Gamma_2)$.

I will do this by showing that, given $\Gamma_1$ without labels, I can recover $Y(\Gamma_1)$ uniquely up to conjugacy in $S_n$.

The crucial observation is that in $\Gamma(S_n,A)$, an element at distance 2 from the identity is either a 3-cycle or a product of two disjoint transpositions. If it is a product of two distinct transpositions, then there will be exactly two paths of length 2 joining it with the identity (in other words, it will be contained in a unique $4$-cycle with the identity). If it is a 3-cycle, there will be exactly either one or three paths of length 2 joining it to the identity.

First, label one vertex of $\Gamma_1$ "1" (think of it as the identity) Then, use the preceding fact to split vertices at distance two from 1 into two classes, which we will call "3-cycles" and "2 disjoint transpositions"identity). Now, labels the neighbours of 1 with $x_1,\ldots,x_k$ (where $k$ is the valency of $\Gamma$). We think of these as being undetermined transpositions. By the argument above, $x_i$ and $x_j$ commute if and only if they are contained in a unique $4$-cycle with the identity. We can now construct $Y(\Gamma_1$), in a unique way up to conjugacy in $S_n$.

1

I claim the answer to your questin is yes. This is my first time posting on mathoverflow. I hope my latex goes ok.

Given $\Gamma(S_n,A)$, build an auxiliary graph $X(\Gamma(S_n,A))$, with vertex set ${1,\ldots,n}$ and two vertices are adjacent if the corresponding involution is in $A$. Build a second auxiliary graph $Y$ with vertex set the elements of $A$ with an edge between them if they commute. Note that $Y$ is the complement of the line graph of $X$.

Let $\Gamma_1=\Gamma(S_n,A)$ and let $\Gamma_2=\Gamma(S_n,B)$.

We have to show that if $\Gamma_1$ and $\Gamma_2$ are isomorphic, then so are $X(\Gamma_1)$ and $X(\Gamma_2)$. By standard results on line graphs, $X(\Gamma_1)$ and $X(\Gamma_2)$ are isomorphic if and only if $Y(\Gamma_1)$ and $Y(\Gamma_2)$ are. It thus suffices to show that if $\Gamma_1$ and $\Gamma_2$ are isomorphic, then so are $Y(\Gamma_1)$ and $Y(\Gamma_2)$.

I will do this by showing that, given $\Gamma_1$ without labels, I can recover $Y(\Gamma_1)$ uniquely up to conjugacy in $S_n$.

The crucial observation is that in $\Gamma(S_n,A)$, an element at distance 2 from the identity is either a 3-cycle or a product of two disjoint transpositions. If it is a product of two distinct transpositions, then there will be exactly two paths of length 2 joining it with the identity (in other words, it will be contained in a unique $4$-cycle with the identity). If it is a 3-cycle, there will be exactly either one or three paths of length 2 joining it to the identity.

First, label one vertex of $\Gamma_1$ "1" (think of it as the identity) Then, use the preceding fact to split vertices at distance two from 1 into two classes, which we will call "3-cycles" and "2 disjoint transpositions".

Now, labels the neighbours of 1 with $x_1,\ldots,x_k$ (where $k$ is the valency of $\Gamma$). We think of these as being undetermined transpositions. By the argument above, $x_i$ and $x_j$ commute if and only if they are contained in a unique $4$-cycle with the identity. We can now construct $Y(\Gamma_1$), in a unique way up to conjugacy in $S_n$.