There are several sorts of graphs referred to as "star graphs" in mathematics, computer science, and information processing. The most common sort of star is the star graph defined as the complete bipartite graph .
A completely different star graph, here termed the permutation star graph (and equivalent to the arrangement graph) has been defined as the graph whose vertices are the permutations of and where vertices are connected by edges whenever two permutations are related by swapping a pair of elements (Akers et al. 1987, Akl and Qiu 1991, Palis et al. 1994, Rajasekaran and Wei 1997). Such graphs are regular of vertex degree , and have graph diameter (Akers et al. 1987, Rajasekaran and Wei 1997), where is the floor function. They are also vertextransitive, edgetransitive, and arctransitive.
A generalization of the permutation star graph was considered by Chiang and Chen (1995). This type of graph includes the permutation star graph (and hence the arrangement graph ) as the special case .
The permutation star graph is regular of vertex degree , has vertex count , and graph diameter
(1)

(Chiang and Chen 1995). is vertextransitive, but neither edgetransitive nor arctransitive for .
The permutation star graph is implemented in the Wolfram Language as GraphData["PermutationStar", n, k].
Special cases are illustrated above and summarized in the following table.
(1,0)  singleton graph 
(2,1)  path graph 
(3,2)  cycle graph 
(4,2)  truncated tetrahedral graph 
(4,3)  Nauru graph 
arrangement graph 