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

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 SizeFormat
Counting Permutation Graphs .pdf855.7 kBAdobe PDFView/Open
Recommend this item

Similar Items from Core Recommender Database

Google ScholarTM

Check

views 13 in Shams Scholar
downloads 5 in Shams Scholar
COUNTING PERMUTATION GRAPHS


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