Graph-theoretic properties of inversion-transpositions

Katanaga, Atsuko (Iwate University)
Shiratama, Takahiro

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 14, No 1 (2026): Electronic Journal of Graph Theory and Applications

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.