CHARACTERIZATION AND ENUMERATION OF 3-REGULAR PERMUTATION GRAPHS
Aysel Erey, Zachary Gershkoff, Amanda Lohss, Ranjan Rohatgi · Rocky Mountain Journal of Mathematics · 2025
A permutation graph is a graph that can be derived from a permutation, where the vertices correspond to letters of the permutation, and the edges represent pairs of letters whose order has been reversed by the permutation. We provide a construction for every 3-regular permutation graph, and we prove that there are infinitely many connected r-regular permutation graphs for r≥3 as well. Finally, we enumerate all 3-regular permutation graphs on n vertices.