Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-04T21:00:28.414Z Has data issue: false hasContentIssue false
  • English
  • Français

Enumeration of self-converse digraphs

Published online by Cambridge University Press:  26 February 2010

F. Harary  and
E. M. Palmer
F. Harary
Affiliation:
The University of Michigan.
E. M. Palmer
Affiliation:
The University of Michigan.
Get access

Extract

How many digraphs are isomorphic with their own converses? Our object is to derive a formula for the counting polynomial dp′(x) which has as the coefficient of xq, the number of “self-converse” digraphs with p points and q lines. Such a digraph D has the property that its converse digraph D′ (obtained from D by reversing the orientation of all lines) is isomorphic to D. The derivation uses the classical enumeration theorem of Pólya [9[ as applied to a restriction of the power group [6] wherein the permutations act only on 1–1 functions.

Type
Research Article
Information
Mathematika , Volume 13 , Issue 2 , December 1966 , pp. 151 - 157
Copyright
Copyright © University College London 1966

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. de Bruijn, N. G., “Pólya's theory of counting”, Chapter 5 in Applied Combinatorial Mathematics, Beckenbach, E. F. (ed.) (New York, 1964), pp. 144–184.Google Scholar
2. Harary, F., “The number of linear, directed, rooted and connected graphs”, Trans. American Math. Soc, 78 (1955), 445–463.CrossRefGoogle Scholar
3. Harary, F., “Structural duality”, Behavioral Science, 2 (1957), 255–265.CrossRefGoogle Scholar
4. Harary, F., A seminar on graph theory (New York, 1967), to appear.Google Scholar
5. Norman, F., Cartwright, D., Structural models: an introduction to the theory of directed graphs (New York, 1965).Google Scholar
6. Harary, F. and Palmer, E. M., “The power group of two permutation groups”, Proc. Nat. Acad. Sci. U.S.A., 54 (1965), 680–682.CrossRefGoogle ScholarPubMed
7. Harary, F. and Palmer, E. M., “The power group enumeration theorem”, J. Combinatorial theory, 1 (1966), 157–173.CrossRefGoogle Scholar
8. Harary, F. and Palmer, E. M., “The groups of the small digraphs”, J. Indian Stat. Assoc, to appear.Google Scholar
9. Pólya, G., “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen”, Acta Math., 68 (1937), 145–254.CrossRefGoogle Scholar
10. Bead, R. C., “On the number of self–complementary graphs and digraphs”, Journal London Math. Soc, 38 (1963), 99–104.Google Scholar
11. Rota, G. C., “On the foundations of combinatorial theory, I. Theory of Mobius functions”, Z. Wahrscheinlichkeitstheorie, 2 (1964), 340–368.CrossRefGoogle Scholar