Characterization and Construction of Permutation Graphs


If is a permutation of , the graph has vertices where xy is an edge of if and only if (x, y) or (y, x) is an inversion of . Any graph isomorphic to is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of forbidden induced subgraphs. In 1971 Pnueli, Lempel, and Even showed that a graph is a permutation graph if and only if both the graph and its complement have transitive orientations. In 2010 Limouzy characterized permutation graphs in terms of forbidden Seidel minors. In this paper, we characterize permutation graphs in terms of a cohesive order of its vertices. We show that only the caterpillars are permutation graphs among the trees. A simple method of constructing permutation graphs is also presented here.

Share and Cite:

S. Gervacio, T. Rapanut and P. Ramos, "Characterization and Construction of Permutation Graphs," Open Journal of Discrete Mathematics, Vol. 3 No. 1, 2013, pp. 33-38. doi: 10.4236/ojdm.2013.31007.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] P. C. F. Ramos, “On Graphs of Inversions of Permutations,” Master’s Thesis, University of the Philippines, Baguio City, 2012.
[2] S. Skiena, “Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica,” Addison-Wesley, Reading, 1990.
[3] T. Gallai, “Transitiv Orientierbare Graphen,” Acta Mathematica Academiae Scientiarum Hungarica, Vol. 18, No. 1-2, 1967, pp. 25-66. doi:10.1007/BF02020961
[4] A. Pnueli, A. Lempel and S. Even, “Transitive Orientation of Graphs and Identification of Permutation Graphs,” Canadian Journal of Mathematics, Vol. 23, No. 1, 1971, pp 160-175. doi:10.4153/CJM-1971-016-5
[5] V. Limouzy, “Seidel Minor, Permutation Graphs and Combinatorial Properties,” In: Lecture Notes in Computer Science Volume 6506, Springer, Berlin, 2010, pp. 194-205.
[6] F. Harary, “Graph Theory,” Addison-Wesley Publishing Company, Boston, 1969.
[7] J. W. Moon, “Topics on Tournaments,” Holt, Rinehart and Winston, New York, 1968.
[8] S. V. Gervacio, “Tournament Score Sequences,” Annals of the New York Academy of Sciences, Vol. 576, Graph Theory and Its Applications, East and West: Proceedings of 1st China-USA International Graph Theory Conference, Jinan, China, June 1986, pp. 200-202.
[9] F. Harary and A. J. Schwenk, “The Number of Caterpillars,” Discrete Mathematics, Vol. 6, No. 4, 1973, pp 359- 365. doi:10.1016/0012-365X(73)90067-8

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.