Original version
The Art of Discrete and Applied Mathematics. 2023, DOI: https://doi.org/10.26493/2590-9770.1536.8db
Abstract
Permutation graphs are graphs associated with permutations where edges represent inversions. We study different classes of permutation graphs and isomorphic permutation graphs. A complete answer of a basic isomorphism question is given for trees. A connection to the majorization order for integer partitions is established, in connection with the notion of inversion vectors. Finally, we study special transitivity properties related to inversions of permutations.