Graph-theoretic properties of inversion-transpositions - Atsuko Katanaga; Takahiro Shiratama (Electronic Journal of Graph Theory and Applications (EJGTA), 2026)
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.