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 vertex-transitive, edge-transitive, and arc-transitive.
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 vertex-transitive, but neither edge-transitive nor arc-transitive 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  |
-Cube." In Proc. International Conference of Parallel Processing, pp. 393-400, 1987.Akl, S. G. and Qiu, K. "Data Communication and Computational Geometry on the Star and Pancake Interconnection Networks." Technical Report TR 91-301, Dept. of Computing and Information Science, Queen's University at Kingston, Ontario, Canada. May 1991.Chiang, W.-K. and Chen, R.-J. "The 
-Star Graph: A Generalized Star Graph." Information Proc. Lett. 56, 259-264, 1995.Palis, M.; Rajasekaran, S.; and Wei, D. S. L. "Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks." J. Parallel Distrib. Comput. 20, 145-157, 1994.Rajasekaran, S. and Wei, D. S. L. "Selection, Routing, and Sorting on the Star Graph." J. Parallel Distrib. Comput. 41, 225-233, 1997.