TOPICS

# 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 -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

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

## Explore with Wolfram|Alpha

More things to try:

## References

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

## 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