AbstractIn 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(seech. 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  is not correct.
|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|
Recommend this item
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.