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.
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
Title | COUNTING PERMUTATION GRAPHS | Authors | BAYOUMI I. BAYOUMI MOHAMED H. EL-ZAHAR ; Khamis, Soheir | 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 |
Attached Files
File | Description | Size | Format | |
---|---|---|---|---|
Counting Permutation Graphs .pdf | 855.7 kB | Adobe PDF | View/Open |
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.