Characterization and Construction of Permutation Graphs

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.

Share and Cite:

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

1. Introduction

A bijection of to itself is called a permutation of order. We shall write

to mean that for. We shall denote by the set of all permutations of.

An inversion of is an ordered pair where

but. Equivalently, is an inversion if and only if and.

Definition 1.1 Let. 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.

The term graph of inversions was used by Ramos in [1]. For our purpose in this paper, any graph isomorphic to for some permutation will be called a permutation graph. There is an implementation PermutationGraph[p] in the Combinatorica package of Mathematica [2] that creates the permutation graph.

In 1967 Gallai [3] characterized permutation graphs in terms of forbidden induced subgraphs. In 1971 Pnueli, Lempel, and Even [4] showed that a graph is a permutation graph if and only if both and its complement have transitive orientations. Recently in 2010 Limouzy [5] gave a characterization of permutation graphs in terms of forbidden Seidel minors.

A characterization of permutation graphs in terms of cohesive vertex-set order is established in this paper. We prove that the only permutation graphs among the trees are the caterpillars. In addition, we describe a simple method of constructing permutation graphs.

2. Cohesive Vertex-Set Order

The vertex-set of a graph will be denoted by while the edge-set will be denoted by. An edge with end-vertices and will be denoted by or. For graph theoretic terms used here without definition, the book by Harary [6] may be referred to.

Consider the permutation. The inversions of are, , , , , and. It is convenient to draw the graph with the vertices in a line following their arrangement in. A drawing of is shown in Figure 1.

There are some important properties of the drawing that we need to take note of.

(a) If and are two edges of the graph where lies between and in the drawing, then is also an edge.

Figure 1. Permutation graph,.

(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.

We define more precisely the properties that we observed.

Definition 2.1 Let be a graph of order. An arrangement of the vertices of is called a cohesive vertex-set order of (or simply cohesive order) if the following conditions are satisfied:

(a) If and, , then .

(b) If and, then or.

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.

Lemma 2.1 Let be a graph. Then is a cohesive order of if and only if is a cohesive order of.

Proof. Let be a cohesive order of. We claim that the same is a cohesive order of. To prove for, let and be vertices of such that. Then and are not edges in. By property of a cohesive order, the edge is not in. Hence, is an edge of. To prove for, let be an edge of with. Let be an integer such that. Since is in, then it is not in. By property of a cohesive order (for) the edges and cannot be both in. Hence at least one of them is in.

The converse follows since.

The next result follows easily from the definition of permutation graph and cohesive order. We shall omit the proof of this theorem.

Theorem 2.1 Let. Then

is a cohesive order of the permutation graph.

Note that is a cohesive order of a graph if and only if is a cohesive order of.

To assign a direction to an edge of a graph means to change to either the ordered pair or the ordered pair.

Definition 2.2 An orientation of a graph is the digraph obtained by assigning a direction to each edge of. The directed edges, which are ordered pairs, are called arcs.

A digraph is said to be transitive if is an arc of whenever and are arcs in.

In a digraph, the out-degree of a vertex, denoted by or simply is the numnber of vertices in such that is an arc in. The in-degree of, denoted by or is the number of vertices in such that is an arc in.

An oriented complete graph is called a tournament [7]. The score of a vertex in a tournament, denoted by is defined by. The score sequence of a tournament is the sequence of scores arranged in non-decreasing order.

The following theorem [8] is not difficult, and is stated without proof.

Theorem 2.2 Let be a tournament of order. The following statements are equivalent:

1) is transitive.

2) For all vertices and in, if is an arc of, then.

3) For all vertices and in, if, then is an arc of.

4) The score sequence of is.

Our main result, which characterizes permutation graphs, is the following theorem.

Theorem 2.3 A graph is a permutation graph if and only if it has a cohesive order.

Proof. If is a permutation graph, then is isomorphic to for some permutation. By Theorem 2.1, is a a cohesive order of. Let be an isomorphism of to. Then is a cohesive order of.

Conversely, let be a graph with a cohesive order. Orient to obtain a digraph as follows: For each edge in, assign the direction if; otherwise assign the direction

.

By property of a cohesive order, it follows that is transitive. Extend to a tournament by orienting the complement of as follows: If but is not in, assign the direction to the edge in. By Lemma 2.1 is a cohesive order of. So likewise, the orientation of obtained in this manner is also transitive. Let us denote this digraph by.

The union of and is an orientation of. Since is complete, then is a tournament. We claim that is a transitive tournament. Let and be arcs of. If both arcs belong to or to, then is in because both and are transitive. So let us assume that one of the arcs belong to and the other arc belong to. Without loss of generality, assume that is an arc in, and is an arc in. If is in, we are done. If is not in, then is in. Since is transitive and, are in, then is in. This is a contradiction because is in.

By Theorem 2.2, the score sequence of is . Let be the permutation defined by, where is the score of in. We claim that the mapping is an isomorphism of to.

The mapping is bijective since the scores of the vertices are distinct. It remains to show that preserves adjacency. Let be an edge of, where. In we have the arc. Since the tournament is transitive, then by Theorem 2.2,

. Hence, is an inversion of

. Therefore, and are adjacent in. Conversely, let be an edge in. Then either or is an inversion. Without loss of generality, assume that is an inversion. Let and, where. Since is an inversion, we have, or. Therefore, the arc is in. Since, the arc must be in. Consequently, the edge is in.

Here is an illustration of the constructive proof of Theorem 2.3. Consider the graph shown in Figure 2 with a cohesive order.

To be able to follow the discussion in the proof of theorem without difficulty, let

.

Using the bottom drawing in Figure 2, we construct a digraph by directing all edges from left to right. For two vertices not adjacent in, we assign the arc that goes from right to left. Then the result is a transitive tournament. It is not difficult to get the score of any vertex in this tournament. We simply count the eastbound arcs and the westbound arcs with a fixed tail. Consider for example,. The number of eastbound arcs with tail at is 3. The number of westbound arcs is simply the number of vertices to its left that are not adjacent to to. The table below summarizes the scores of the vertices.

 Vertex v1 = x2 v2 = x4 v3 = x1 v4 = x3 v5 = x5 Score, s(vi) 2 4 0 1 3

Take the permutation defined by. Then. The permutation graph is shown in Figure 3.

3. Construction and Examples of Permutation Graphs

Some fundamental facts about permutation graphs are given in the next theorem.

Theorem 3.1 Let be a graph. The following are equivalent:

(a) is a permutation graph.

(b) is a permutation graph.

Figure 2. A graph with cohesive order .

Figure 3. The permutation graph,.

(c) Every induced subgraph of is a permutation graph.

(d) Every connected component of is a permutation graph.

Proof. From Lemma 2.1, has a cohesive order if and only if has a cohesive order. Therefore, (a) and (b) are equivalent.

If is a cohesive order of, then the subgraph of induced by a set of vertices

, where has cohesive order and therefore is a permutation graph. Hence, (a) and (c) are equivalent.

Statement (c) implies statement (d) because a connected component of is an induced subgraph of.

It remains to show that (d) implies any of (a), (b), (c). Let have connected components and let be the order of. Let

be a cohesive order of. Then

is a cohesive order of. Therefore is a permutation graph.

We can now identify permutation graphs through the existence of a cohesive order. Moreover, we can even determine a permutation that generates a permutation graph isomorphic to the graph having a cohesive order.

Paths and stars are permutation graphs because they have cohesive orders as illustrated in Figure 4.

In the drawing of the path, we have

, etc.

Condition (a) is vacuously satisfied because there is no pair of arcs, and such that. Note for example that is an arc and the vertices 1 and 4 are between 2 and 3 in the drawing. We have 1 adjacent to 2 and 4 adjacent to 3. This illustrates condition (b).

In the drawing of the star we see that for every arc where all vertices with are between and. Moreover, the vertex is adjacent to 0. Therefore condition (b) is satisfied. Condition (a) is satisfied vacuously.

Paths and stars are trees but not all trees are permutation graphs. Consider the tree formed by subdividing each edge of the star into two edges, as shown in Figure 5.

It is not difficult to argue indirectly that has no cohesive order. Therefore this is not a permutation graph. This result is also established by Limouzy [5] where he used the symbol for.

Harary and Schwenk [9] defined a caterpillar to be a tree with the property that the removal of all pendant vertices results into a path. Figure 6 shows a caterpillar with 25 pendant vertices. The removal of these 25 pendant vertices yields the path.

The next lemma is easy and its proof is omitted.

Lemma 3.1 A tree is a caterpillar if and only if it does not contain as a subgraph.

Theorem 3.2 A tree is a permutation graph if and only if it is a caterpillar.

Proof. A tree that contains is not a permutation

Figure 4. Cohesive order of paths and stars.

Star, K1,3

Figure 5. The tree obtained by subdividing the edges of.

Figure 6. A caterpillar with 25 pendant vertices.

graph because is not a permutation graph. Therefore, all we need to show is that a caterpillar is a permutation graph. Let be a caterpillar and let be the path obtained from by removing the pendant vertices. If, then is either the trivial graph or the star for some. Since the trivial graph and the stars are permutation graphs, we assume that.

Let us form the cohesive order of as shown in Figure 4. Let be a set of pendant vertices of all adjacent to the same vertex of. If is odd, we insert the vertices in immediately to the left of the vertex of the path (see Figure 4). If is even we insert the vertices in between and. The result is a cohesive order of. Therefore is a permutation graph.

Definition 3.1 Let be a graph with vertices and let be a collection of arbitrary graphs. The composition by of , denoted by is the graph formed by taking the disjoint union of the graphs and then adding all edges of the form where is in, is in whenever is an edge of.

If each is equal to a fixed graph, we use the symbol to denote the composition.

The sum of two graphs and , denoted by is formed by taking the disjoint union of and and then adding all edges of the form where and. Thus, the composition is formed by taking the disjoint union of the graphs and then forming the sum if the associated vertices and of are adjacent.

Theorem 3.3 Let be a graph of order and let be arbitrary graphs. Then

is a permutation graph if and only if, are permutation graphs.

Proof. First, assume that is a permutation graph. Each graph is an induced subgraph of. Therefore, each is a permutation graph. If we take a vertex from each, then the subgraph induced by these vertices is isomorphic to. Therefore is a permutation graph.

Conversely, assume that, are all permutation graphs. Then there is a cohesive order of. Let be the order of. Then the vertices of has a cohesive order

.

It is easy to check that is a cohesive order of.

Theorem 3.3 actually gives us an easy way of constructing permutation graphs by composition. To illustrate this, let be the star with central vertex and pendant vertices, then

is shown in Figure 7.

All graphs of order at most 4 are permutation graphs [1]. Therefore, is a permutation graph.

Every graph of order may be written as

and.

If these are the only ways can be written as a composition, then we say that is prime.

It is easy to see that among the complete graphs, only and are prime permutation graphs.

Among trees with diameter not exceeding 3, it is easy to check that only the paths, , and are prime permutation graphs. These are all caterpillars that do not have two pendant vertices adjacent to a common vertex. Note that which is excluded from the list is a caterpillar with two pendant vertices having a common neighbor.

Theorem 3.4 A tree is a prime permutation graph if and only if it is a caterpillar where no two pendant vertices have a common neighbor.

Proof. In view of our observation about trees with diameter not exceeding 3, we assume throughout that T has diameter at least 4.

Let be a tree of order. Assume that is a prime permutation graph. By Theorem 3.2 T is a caterpillar. Suppose that and are pendant vertices with a common neighbor. Let be the tree obtained from by identifying and. Let be the vertices of Without loss of generality, assume that is the vertex resulting from the identification of and. Let be the graph with two vertices but without an edge, and let be the trivial graph for. Then

.

This contradicts the fact that is prime.

Figure 7. The composition by of.

Conversely, assume that is a caterpillar with no two pendant vertices having a common neighbor. Suppose that is a not a prime permutation graph. Then for some non-trivial graph with vertices

,.

Without loss of generality, we may assume that contains at least two vertices. Now, must be connected for otherwise, is disconnected. Let be adjacent to without loss of generality. Then

is a subgraph of. If has at least two vertices, then there will be a cycle in. Therefore, has only one vertex. In, cannot be adjacent anymore to any other vertex for otherwise, we would also create a cycle of length 4. Now consider. There cannot be adjacent vertices in for otherwise we will create a cycle of length 3. But then all vertices in are pendant vertices of and they have a common neighbor, the vertex in. This is a contradiction.

Theorem 3.5 Let be a decomposable permutation graph. Then there exists a non-trivial prime permutation graph and permutation graphs

which are subgraphs of such that

.

Proof. Let

be a decomposition of, where is non-trivial. If we take one vertex from each, then the subgraph induced by these vertices is isomorphic to. Hence, must be a permutation graph. Each is an induced subgraph of. Therefore, each is a permutation graph. Assume that has smallest order among all such decompositions of. We claim that is a prime permutation graph. Suppose that is not prime. Let

be a decomposition of, where is non-trivial. Since is a decomposition of and vertices of are the induced subgraphs then each is a associated with subset of. We may assume that is an induced subgraph of. Hence . But this contradicts the choice of. Therefore, must be a prime permutation graph.

4. Concluding Remarks

Theorem 3.5 is a fair structural description of a permutation graph. Each in the decomposition

is a permutation graph and so is itself prime permutation graph or a composition of permutation graphs by a prime permutation graph. So we see that a permutation graph is expressible in terms of prime permutation graphs by compositions.

We have determined already the prime permutation trees, given in Theorem 3.4. One interesting problem to consider is the characterization of prime permutation graphs.

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