On the Genus of the Star Graph

The star graph \(S_n\) is a graph with \(S_n\), the set of all permutations over \(\{1, \ldots, n\}\) as its vertex set; two vertices \(\pi_1\) and \(\pi_2\) are connected if \(\pi_1\) can be obtained from \(\pi_2\) by swapping the first element of \(\pi_2\) with one of the other \(n-1\) elements. In this paper we establish the genus of the star graph. We show that the genus, \(g_n\) of \(S_n\) is exactly equal to \(n!(n-4)/6+1\) by establishing a lower bound and inductively giving a drawing on a surface of appropriate genus.