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 |