Characterization and Construction of Permutation Graphs

• 作者: Phoebe Chloe F. Ramos Severino V. Gervacio Teofina A. Rapanut
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: PERMUTATION Inversion PERMUTATION GRAPH COHESIVE Order Oriented GRAPH TOURNAMENT SCORE Sequence CATERPILLAR GRAPH Composition
• 年，卷（期）: 2013,（1）
• 页码范围: 33-38
• 页数: 6页
• 分类号: O1

摘要

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.