Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-20T06:40:18.118Z Has data issue: false hasContentIssue false
  • English
  • Français

Enumeration of Graphs with given Partition

Published online by Cambridge University Press:  20 November 2018

K. R. Parthasarathy
K. R. Parthasarathy*
Affiliation:
Indian Institute of Technology, Madras
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.

In this paper we use a generalized form of Polya's theorem (1) to obtain generating functions for the number of ordinary graphs with given partition and for the number of bicoloured graphs with given bipartition. Both the points and lines of the graphs are taken as unlabelled. These graph enumeration problems were proposed by Harary in his review article (4). Read (7, 8) solved the problem for unlabelled general graphs and labelled ordinary graphs.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 20 , 1968 , pp. 40 - 47
Copyright
Copyright © Canadian Mathematical Society 1968

References

1. de Bruijn, N. G. Generalization of Polya1 s fundamental theorem in enumerative combinatorial analysis, Indag. Math., 21 (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 bicoloured graphs, Pacific J. Math., 8 (1958), 743–755.Google Scholar
4. Harary, F., Unsolved problems in the enumeration of graphs, Publ. Math. Inst. Hung. Acad. Sci., 5 (1960), 63–95.Google Scholar
5. McMahon, P. A., Combinatory analysis, Vol. I (Cambridge 1915; New York 1960).Google Scholar
6. Mirsky, L., Inequalities and existence theorems in the theory of matrices, J. Math. Anal, and Appl., 9 (1964), 99–118.Google Scholar
7. Read, R. C., The enumeration of locally restricted graphs I, J. London Math. Soc, 84 (1959), 417–436.Google Scholar
8. Read, R. C., The enumeration of locally restricted graphs II, J. London Math. Soc, 85 (1960), 344–351.Google Scholar
9. Ryser, H. J., Matrices of zeros and ones, Bull. Amer. Math. Soc, 66 (1960), 442–464.Google Scholar