On Classification of Permutation Graphs
Denis N. King’ang’I *
Department of Mathematics & Computer Science, University of Eldoret, Eldama Ravine, Kenya.
Sammy W. Musundi
Department of Physical Sciences, Chuka University, Chuka, Kenya.
Fancy Nyabate
Department of Physical Sciences, Chuka University, Chuka, Kenya.
*Author to whom correspondence should be addressed.
Abstract
Graph theory constitutes a prominent branch of discrete mathematics that has undergone extensive theoretical advancement and has found wide-ranging applications across diverse disciplines, including computer science, chemistry, biology, and operations research. Consequently, it has attracted considerable scholarly interest, leading to substantial research activity in areas such as graph labelling, graph colouring, combinatorics, graph isomorphism, matroid theory, and graph representations, among others. Construction of other classes of permutations graphs and determining the properties of the emerging classes has also been of interest to many researchers. Fancy developed a class of permutations and labeled it the \(U^{n}_{x_k}\) - permutations. They also determined some algebraic properties of these \(U^{n}_{x_k}\) - permutations and suggested for more analysis on these graphs. This paper extends the work of Fancy by performing more analysis on the \(U^{n}_{x_k}\) - permutations. Graphs are constructed from some \(U^{n}_{x_k}\) - permutations and analysis of these graphs is performed. Some graph properties are obtained, including isomorphism, paths and components. The graphs from the permutations forming groups are found to exhibit isomorphisim and to have some interesting patterns.
Keywords: Permutation, graph, isomorphism, path, cycle