Transposition Graph


A transposition graph G_n is a graph whose nodes correspond to permutations and edges to permutations that differ by exactly one transposition (Skiena 1990, p. 9, Clark 2005).

The transposition graph G_n has vertex count n!, edge count (n; 2)^2(n-2)! (for n>1), and is regular of degree (n; 2) (Clark 2005). All cycles in transposition graphs are of even length, making them bipartite.

The transposition graph of a multiset is always Hamiltonian (Chase 1973).

Special cases are summarized in the table below.

See also

Permutation, Transposition

Explore with Wolfram|Alpha


Chase, P. J. "Transposition Graphs." SIAM J. Comput. 2, 128-133, 1973.Clark, D. "Transposition Graphs: An Intuitive Approach to the Parity Theorem for Permutations." Math. Mag. 78, 124-130, 2005.Ganesan, A. "Automorphism Group of the Complete Transposition Graph." 27 Apr 2014., S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 9-10, 1990.

Referenced on Wolfram|Alpha

Transposition Graph

Cite this as:

Weisstein, Eric W. "Transposition Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications