On the genus of the star graph. (English) Zbl 0993.05053

Author’s abstract: The star graph \({\mathcal S}_n\) is a graph with \(S_n\), the set of all permutations over \(\{ 1,\dots ,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 _1\) 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 \({\mathcal 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.


05C10 Planar graphs; geometric and topological aspects of graph theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
94C15 Applications of graph theory to circuits and networks
57M15 Relations of low-dimensional topology with graph theory