Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-20T16:29:01.710Z Has data issue: false hasContentIssue false
  • English
  • Français

Enumeration of Locally Restricted Digraphs

Published online by Cambridge University Press:  20 November 2018

Frank Harary  and
Ed Palmer
Frank Harary
Affiliation:
The University of Michigan, Ann Arbor, Michigan
Ed Palmer
Affiliation:
The University of Michigan, Ann Arbor, Michigan
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Among the unsolved problems in graphical enumeration listed in (4) is included the determination of the number of graphs and digraphs with a given partition. Parthasarathy (9) has developed a formulation for counting graphs with a given partition by making a suitable modification of the method given in (2) for the enumeration of graphs. We present here an analogous modification that leads to a formula for the number of digraphs with a given partition. Not surprisingly, the main combinatorial device for this purpose is provided by the classical theorem due to Pólya.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 18 , 1966 , pp. 853 - 860
Copyright
Copyright © Canadian Mathematical Society 1966

References

1. de Bruijn, N. G., Generalization of Pólya's fundamental theorem in enumerative combinatorial analysis, Nederl. Akad. Wetensch. Proc. Ser. A, 62 (1959), 59–69.Google Scholar
2. Harary, F., The number of linear, directed, rooted and connected graphs, Trans. Amer. Math. Soc., 78 (1955), 445–463.Google Scholar
3. Harary, F., On the number of bicolored graphs, Pacific J. Math., 8 (1958), 743–755.Google Scholar
4. Harary, F., Combinatorial problems in graphical enumeration, chap. 6 in Applied combinatorial mathematics, edited by Beckenbach, E. F. (New York, 1964), pp. 185–217.Google Scholar
5. Harary, F., A seminar on graph theory (New York, 1967). to appear.Google Scholar
6. Harary, F., Norman, R., and Cartwright, D., Structural models: An introduction to the theory of directed graphs (New York, 1965).Google Scholar
7. Harary, F. and Palmer, E., The power group enumeration theorem, J. Combinatorial Theory, 1 (1966), to appear.Google Scholar
8. Katz, L. and Powell, J. H., The number of locally restricted directed graphs, Proc. Amer. Math. Soc., 5 (1954), 621–626.Google Scholar
9. Parthasarathy, K. R., Enumeration of ordinary graphs with given partition, Can. J. Math., to appear.Google Scholar
10. Pólya, G., Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen, Acta Math., 68 (1937), 145–254.Google Scholar
11. Sukhatme, P. V., On bipartitional functions, Phil. Trans. Roy. Soc. London, Ser. A, 237 (1938), 375–409.Google Scholar