Graph-theoretic properties of inversion-transpositions

<span>Dénés established the connection between labeled trees in Graph Theory and factorizations of cyclic permutations by means of transpositions. In this paper, we introduce the notion of an inversion-transposition, which has both the properties of an inversion and a transposition. For a cyclic permutation, we define the graph associated with each minimal representation using only inversion-transpositions and consider the properties. The main result is that a spanning tree T reconstructs the original permutation if and only if the sum over all vertices v of the distance in T between v and σ(v) equals 2(n - 1), which provides a precise reconstruction criterion.</span>