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

CORE Recommender
6
Views


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