✦ LIBER ✦

On testing isomorphism of permutation graphs

✍ Scribed by Charles J. Colbourn

Publisher: John Wiley and Sons
Year: 1981
Tongue: English
Weight: 530 KB
Volume: 11
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230110103

No coin nor oath required. For personal study only.

✦ Synopsis

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 uniquely orientable induced subgraphs.

📜 SIMILAR VOLUMES

Isomorphism classes of cycle permutation

Isomorphism classes of cycle permutation graphs

✍ Jin Ho Kwak; Jaeun Lee 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 769 KB

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 gr

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

On diameter of permutation graphs

✍ Gu, Weizhen 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

Let G be a connected graph with n vertices. Let a be a permutation in S n . The a-generalized graph over G, denoted by P a (G), consists of two disjoint, identical copies of G along with edges £a(£). In this paper, we investigated the relation between diameter of P a (G) and diameter of G for any pe

Initial vertex partitioning and testing

Initial vertex partitioning and testing isomorphism of graphs and digraphs

✍ Kabekode V. S. Bhat; M. H. Rahnavard 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 531 KB

On 4-isomorphisms of graphs

✍ G Lassmann 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 126 KB

On restricted connectivities of permutat

On restricted connectivities of permutation graphs

✍ C. Balbuena; X. Marcote; P. García-Vázquez 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB