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.

MSC:

 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