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