The complement of a graph, denoted by has the same vertex-set as and two distinct vertices and form the edge in if and only if is not an edge in. An arrangement of the vertices of is called a cohesive vertex-set order of (or simply cohesive order ) if the following conditions are satisfied: We define more precisely the properties that we observed.ĭefinition 2.1 Let be a graph of order. (b) If is an edge and is a vertex that lies between and in the drawing, then either is an edge or is an edge. (a) If and are two edges of the graph where lies between and in the drawing, then is also an edge. There are some important properties of the drawing that we need to take note of. It is convenient to draw the graph with the vertices in a line following their arrangement in. For graph theoretic terms used here without definition, the book by Harary may be referred to.Ĭonsider the permutation. An edge with end-vertices and will be denoted by or. The vertex-set of a graph will be denoted by while the edge-set will be denoted by. In addition, we describe a simple method of constructing permutation graphs. We prove that the only permutation graphs among the trees are the caterpillars. Recently in 2010 Limouzy gave a characterization of permutation graphs in terms of forbidden Seidel minors.Ī characterization of permutation graphs in terms of cohesive vertex-set order is established in this paper. In 1971 Pnueli, Lempel, and Even showed that a graph is a permutation graph if and only if both and its complement have transitive orientations. In 1967 Gallai characterized permutation graphs in terms of forbidden induced subgraphs. There is an implementation PermutationGraph in the Combinatorica package of Mathematica that creates the permutation graph. For our purpose in this paper, any graph isomorphic to for some permutation will be called a permutation graph. The term graph of inversions was used by Ramos in. The graph of inversions of, denoted by, is the graph with vertices where is an edge of if and only if or is an inversion of. Equivalently, is an inversion if and only if and. We shall denote by the set of all permutations of. A simple method of constructing permutation graphs is also presented here.Ī bijection of to itself is called a permutation of order. We show that only the caterpillars are permutation graphs among the trees. In this paper, we characterize permutation graphs in terms of a cohesive order of its vertices. In 2010 Limouzy characterized permutation graphs in terms of forbidden Seidel minors. 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. Any graph isomorphic to is called a permutation graph. If is a permutation of, the graph has vertices where is an edge of if and only if or is an inversion of. Keywords: Permutation Inversion Permutation Graph Cohesive Order Oriented Graph Tournament Score Sequence Caterpillar Graph Composition 1Department of Mathematics, De La Salle University, Manila, PhilippinesĢDepartment of Mathematics and Computer Science, University of the Philippines, Baguio City, PhilippinesĮmail: Septemrevised Octoaccepted October 25, 2012
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |