ISOMORPHIC DECOMPOSITIONS OF CAYLEY GRAPH ASSOCIATED TO Sn

Let S be a subset of a group G such that 1 =2 S and S = S¡1. The Cayley graph Cay(G; S) associated with G and S is defined to have vertex set G and a vertex f is joined to a vertex g if g¡1f 2 S or equivalently f¡1g 2 S. A decomposition of a graph is a list of subgraphs such that each edge appeares in exactly one subgraph in the list. In addition if all of subgraphs in a decomposition of a graph are isomorphic to H, this decomposition is called H¡decomposition. Also the H-decomposition of G is balanced if every vertex of G is in the same number of copies of H. Furthermore an H¡decomposition fH1;H2; : : : ;Hkg of G is called transitive if for any two copies Hi and Hj of H, there is an automorphism f of G such that f(Hi) = Hj . Let Sn be the symmetric group on the set [n] = f 1; 2; :::; ng and T be the set of all transpositions. In this paper we find an isomorphic decomposition of Cay(Sn; T) into edge disjoint copies of [n 2 ]-Cubes. In addition we show that this decomposition is transitive and balanced. 1.