Characterization and Construction of Permutation Graphs
- 1 Department of Mathematics, De La Salle University, Manila, Philippines
- 2 Department of Mathematics and Computer Science, University of the Philippines, Baguio City, Philippines
- 3 Department of Mathematics and Computer Science, University of the Philippines, Baguio City, Philippines
Abstract
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.
- P. C. F. Ramos, “On Graphs of Inversions of Permutations,” Master’s Thesis, University of the Philippines, Baguio City, 2012.
- S. Skiena, “Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica,” Addison-Wesley, Reading, 1990.
- T. Gallai, “Transitiv Orientierbare Graphen,” Acta Mathematica Academiae Scientiarum Hungarica, Vol. 18, No. 1-2, 1967, pp. 25-66. doi:10.1007/BF02020961
- 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
- V. Limouzy, “Seidel Minor, Permutation Graphs and Combinatorial Properties,” In: Lecture Notes in Computer Science Volume 6506, Springer, Berlin, 2010, pp. 194-205.
- F. Harary, “Graph Theory,” Addison-Wesley Publishing Company, Boston, 1969.
- J. W. Moon, “Topics on Tournaments,” Holt, Rinehart and Winston, New York, 1968.
- 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.
- 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