𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Isomorphism classes of cycle permutation graphs

✍ Scribed by Jin Ho Kwak; Jaeun Lee

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
769 KB
Volume
105
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we construct a cycle permutation graph as a covering graph over the dumbbell graph, and give a new characterization of when two given cycle permutation graphs are isomorphic by a positive or a negative natural isomorphism. Also, we count the isomorphism classes of cycle permutation graphs up to positive natural isomorphism, and find the number of distinct cycle permutation graphs isomorphic to a given cycle permutation graph by a positive/negative natural isomorphism.

As a consequence, we obtain a formula for finding the number of double cosets of the dihedral group in the symmetric group.

πŸ“œ SIMILAR VOLUMES

On testing isomorphism of permutation gr
On testing isomorphism of permutation graphs
✍ Charles J. Colbourn πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 530 KB

## Abstract A polynomial time algorithm for testing isomorphism of permutation graphs (comparability graphs of 2‐dimensional partial orders) is described. It operates by performing two types of simplifying transformations on the graph; the contraction of duplicate vertices and the contraction of un

On the cycle-isomorphism of graphs
On the cycle-isomorphism of graphs
✍ Xingxing Yu πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 336 KB

## Abstract This paper considers conditions ensuring that cycle‐isomorphic graphs are isomorphic. Graphs of connectivity β©Ύ 2 that have no loops were studied in [2] and [4]. Here we characterize all graphs __G__ of connectivity 1 such that every graph that is cycle‐isomorphic to __G__ is also isomor

Enumeration of weak isomorphism classes
Enumeration of weak isomorphism classes of signed graphs
✍ Tadeusz SozaΕ„ski πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 869 KB

## Abstract A signed graph is a graph in which each line has a plus or minus sign. Two signed graphs are said to be weakly isomorphic if their underlying graphs are isomorphic through a mapping under which signs of cycles are preserved, the sign of a cycle being the product of the signs of its line

Equivalence class universal cycles for p
Equivalence class universal cycles for permutations
✍ Glenn Hurlbert; Garth Isaak πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 268 KB

We construct a universal cycle of n-permutations using n + 1 symbols and an equivalence relation based on differences. Moreover a complete family of universal cycles of this kind is constructed.