TOPICS
Search

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
(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}}].

PermutationStarGraph

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

References

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. https://mathworld.wolfram.com/PermutationStarGraph.html