## COUNTING PERMUTATION GRAPHS

BAYOUMI I. BAYOUMI MOHAMED H. EL-ZAHAR ; Khamis, Soheir## Abstract

In this paper the authors enumerate the number of permutation graphs ( up to isomorphism). The counting process depends on the exploitation •of structural decompositions of various sorts of permutations and permutation graphs and a relationship between them, which leads to the properties of those graphs having twice transitive orientations ( prime permutation graphs). According to the results of Pσlya , Riddell(see[4]ch. 2,4), the exact number of specified graphs. g (n), with n vertices is, recu rsively, calculated. Also, the authors found the functional • equation for the generating function ∑_(n≥1)▒g (n)x^n in terms of the generating function for prime permutation graphs. The numbers of permutation graphs with n≤20 are given. These numbers show that the previously known number for n = 10 given in [6] is not correct.

## Other data

Keywords | Permutation , comparability graph, permutation graph, partitive set , prime graph, prime permutation graph, transitive orientation, poset of dimension two, generating function |

Issue Date | 10-Dec-1990 |

Conference | THE 25th ANNUAL CONFERENCE ON STATISTICS, COMPUTER SCIENCE AND OPERATIONS RESEARCH |

URI | http://research.asu.edu.eg/123456789/1142 |

File | Description | Size | Format | |
---|---|---|---|---|

Counting Permutation Graphs .pdf | 855.7 kB | Adobe PDF | View/Open |

CORE Recommender

6

Views

Views

Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.