TITLE:
Characterization and Construction of Permutation Graphs
AUTHORS:
Severino V. Gervacio, Teofina A. Rapanut, Phoebe Chloe F. Ramos
KEYWORDS:
Permutation; Inversion; Permutation Graph; Cohesive Order; Oriented Graph; Tournament Score Sequence; Caterpillar; Graph Composition
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.3 No.1,
January
29,
2013
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.