Words for the Graphs with Permutation-Representation Number at most Three

The graphs with permutation-representation number ($\mathit{\text{prn}}$) at most two are known. While a characterization for the class of graphs with the $\mathit{\text{prn}}$ at most three is an open problem, we summarize the graphs of this class that are known so far. Although it is known that the $\mathit{\text{prn}}$ of trees is at most three, in this work, we devise a polynomial-time algorithm for obtaining a word representing a given tree permutationally. Consequently, we determine the words representing even cycles. Contributing to the class of graphs with the $\mathit{\text{prn}}$ at most three, we determine the $\mathit{\text{prn}}$ as well as the representation number of book graphs.