Graph-theoretic properties of inversion-transpositions

Atsuko Katanaga, Takahiro Shiratama

Abstract


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.

Keywords


graph theory; inversion; transposition; permutation

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.6

References

J. Dènes, “The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences, vol. 4, pp. 63–70, 1959.

M. Eden and M. P. Schützenberger, “Remark on a theorem of Dènes,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences, pp. 353–355, 1962.

F. Harary, Graph Theory, Addison-Wesley Publishing Company, 1969.

A. Hurwitz, “Über Riemannsche flächen mit gegebenen verzweigungspunkte,” Mathematische Annalen, vol. 39, pp. 1–61, 1891.

A. Hurwitz, “Über die anzahal der Reimannschen flächen mit gegebenen verzweigungspunkte,” Mathematische Annalen, vol. 55, pp. 53–66, 1902.

B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, 2001.

P. Moszkowski, “A solution to a problem of Dènes: a bijection between trees and factorizations of cyclic permutations,” European Journal of Combinatorics, vol. 10, pp. 13–16, 1989.

S. Tsujie and R. Uchiumi, “Upper embeddability of graphs and products of transpositions associated with edges,” Ars Mathematica Contemporanea, vol. 25, no. 2, #P2.05, 2025.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats