Characterization and enumeration of 3-regular permutation graphs

Abstract

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 inversions. We provide a construction to show that there are infinitely many connected $r$-regular permutation graphs for $r\ge 3$. We prove that all $3$-regular permutation graphs arise from a similar construction. Finally, we enumerate all $3$-regular permutation graphs on $n$ vertices.

11 pages, 11 figures