Permutation Star Graph

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 n-star graph S_n defined as the complete bipartite graph K_(1,n-1).

A completely different n-star graph, here termed the n-permutation star graph PS_n (and equivalent to the A_(n,n-1)-arrangement graph) has been defined as the graph whose vertices are the n! permutations of {1,...,n} 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 n-1, and have graph diameter |_3(n-1)/2_| (Akers et al. 1987, Rajasekaran and Wei 1997), where |_x_| is the floor function. They are also vertex-transitive, edge-transitive, and arc-transitive.

A generalization S_(n,k) of the n-permutation star graph was considered by Chiang and Chen (1995). This type of graph includes the n-permutation star graph PS_n (and hence the arrangement graph A_(n,n-1)) as the special case S_(n,n-1).

The permutation star graph S_(n,k) is regular of vertex degree n-1, has vertex count n!/(n-k)!, and graph diameter

 d(S_(n,k))={2k-1   for k<=|_n/2_|; |_(n-1)/2_|+k   for k>=|_n/2_|+1

(Chiang and Chen 1995). S_(n,k) is vertex-transitive, but neither edge-transitive nor arc-transitive for k!=n-1.

The (n,k)-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.

See also

Alternating Group Graph, Arrangement Graph, Permutation Graph, Star Graph

Explore with Wolfram|Alpha


Akers, S.; Harel, D.; and Krishnamurthy, B. "The Star Graph: An Attractive Alternative to the n-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 (n,k)-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.

Referenced on Wolfram|Alpha

Permutation Star Graph

Cite this as:

Weisstein, Eric W. "Permutation Star Graph." From MathWorld--A Wolfram Web Resource.