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 52 in Shams Scholar
downloads 21 in Shams Scholar
COUNTING PERMUTATION GRAPHS


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