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

Abbasi, Sarmad

Ars Comb. 55, 217-225 (2000).

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.

Reviewer: Tomáš Kaiser (Plzeň)

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

Keywords:

star graphs; genus; Cayley graphs; interconnection networks; topology