Permutation Star Graph

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

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

(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 [👁 {
, 👁 {
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

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