ON CHARACTERIZATION OF PERMUTATION GRAPHS

Abstract

Graph theory is an area in discrete mathematics with numerous theoretical developments and many applications to practical problems in computer science, chemistry, biology and operational research. As a result, it has attracted much attention to researchers in many dimensions including graph labeling, graph coloring, combinatorics, graph isomorphism, matroid theory and graph representations among others. Many researchers in this area have also worked on permutation graphs paying attention to the properties of cyclic permutation graphs, including crossing numbers and isomorphism. So far isomorphism between two cyclic permutation graphs has been determined by positive and negative natural isomorphism. However, construction of other classes of permutations graphs and establishing an alternative approach for determining isomorphism between permutation graphs as well as finding some properties of permutation graphs would be of significance. The aim of this study was to develop a class of permutations, determine algebraic properties of the permutations, construct permutation graphs and establish some properties of the constructed graphs including isomorphism. A class of [nxk - permutations was first obtained by coming up with a bijection on a finite set, which resulted into permutations. Some algebraic properties were established, in particular, the permutations resulted in an abelian group as well as it formed a subgroup. Graphs were then constructed from these permutations and some properties including symmetry, unique, connectedness, distance and isomorphism determined by enumeration. The results of this research are of significance in other practical areas of application of graphs, including computer science, chemistry, biology, operational research and combinatorics.