Transposition Graph

The transposition graph considered here is the Cayley graph of the symmetric group generated by all transpositions. Equivalently, its vertices are the permutations, with two vertices adjacent when the corresponding permutations differ by exactly one transposition (Skiena 1990, pp. 1-2 and 9-10; Pemmaraju and Skiena 2003, pp. 64-65 and 96; Clark 2005).

More generally, for a set of transpositions, the transposition generating graph has vertex set and an edge iff . The associated Cayley graph is called a complete transposition graph when its transposition generating graph is the complete graph , equivalently when contains all transpositions (Ganesan 2015, Yang 2018). Thus, "complete" describes the generating graph, not the Cayley graph itself. Transposition graphs that are not complete in this sense use a proper subset and join two permutations only when they differ by one of the transpositions in . For the graph generated by all transpositions discussed here, the qualifier "complete" is commonly omitted (Skiena 1990, pp. 1-2 and 9-10; Pemmaraju and Skiena 2003, pp. 64-65 and 96; Clark 2005). The notations (Berestycki 2006, p. 429) and (Baggett and Yan 2026) are used for this Cayley graph on .

The transposition graph has vertex count , edge count (for ), and is regular of degree (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).

A strict Hamilton decomposition of into Hamiltonian cycles alone is possible only when its degree is even, or equivalently when (mod 4) or (mod 4). Under the extended convention allowing one perfect matching when the degree is odd, Shi and Niu (2009) conjectured that every complete transposition graph is a Hamilton decomposable graph. Such a decomposition must contain Hamiltonian cycles and, when (mod 4) or (mod 4), one perfect matching. Shi and Niu (2009) verified the conjecture for and 3, and direct certificates give decompositions also for and 5. The general conjecture remains open.

As partial progress, Hussak (2016) proved that contains at least pairwise edge-disjoint Hamiltonian cycles for every . A full Hamilton decomposition or quasi-Hamilton decomposition requires such cycles, so this result does not settle the conjecture of Shi and Niu. Baggett and Yan (2026) subsequently proved that is paired 2-disjoint-path-coverable and therefore Hamilton-laceable. However, this stronger Hamilton-path property likewise does not provide an edge decomposition.

Special cases are summarized in the table below.

1	singleton graph
2	2-path graph
3	utility graph
4	Reye graph