Permutation Star Graph

A permutation star graph is one of 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 the element in a fixed position, say the first, with an element in any other position (Akers et al. 1987, Akl and Qiu 1991, Palis et al. 1994, Rajasekaran and Wei 1997, Hsieh et al. 2000). 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.

For , is strongly Hamiltonian-laceable (Hsieh et al. 2000). Its two bipartition classes consist of the even permutations and odd permutations, each containing vertices, where . For distinct endpoints, the longest path has length when their permutation signs differ and when their signs agree. Consequently, the detour index is

(1)

The case is exceptional and has detour index 63.

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

(2)

(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