Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T00:47:28.408Z Has data issue: false hasContentIssue false
  • English
  • Français

Labeled Bipartite Blocks

Published online by Cambridge University Press:  20 November 2018

F. Harary  and
R. W. Robinson
F. Harary
Affiliation:
University of Michigan, Ann Arbor, Michigan
R. W. Robinson
Affiliation:
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.

Graphs which are 2-connected have been called blocks in the graph theoretic literature [3] and stars in the parlance of statistical mechanics [1]. They are also called nonseparable graphs, and in this paper include the complete graph K2 on p = 2 points. The standard terminology of graphical enumeration can be found in [3].

When its points are colored using two distinct colors in such a way that adjacent points receive different colors, a graph is called 2-colored. If the colors are considered interchangeable, such a graph is called bicolored. A graph which can be bicolored is called bicolorable. It is obvious that a connected bicolorable graph has a unique bicoloring, and so one can speak of the sizes of its color classes.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 31 , Issue 1 , 01 February 1979 , pp. 60 - 68
Copyright
Copyright © Canadian Mathematical Society 1979

References

1. Ford, G. W. and Uhlenbeck, G. E., Combinatorial problems in the theory of graphs, I, Proc. Nat. Acad. Sci. U.S.A. 42 (1956), 122–128.Google Scholar
2. Gilbert, E. N., Enumeration of labelled graphs, Can. J. Math. 8 (1956), 405–411.Google Scholar
3. Harary, F. and Palmer, E. M., Graphical enumeration (Academic Press, New York, 1973).Google Scholar
4. Melnyk, T. W., Rowlinson, J. S. and Sawford, B. L., The penetrable sphere and related models of liquid-vapour equilibrium, Molecular Physic. 24 (1972), 809–831.Google Scholar
5. Read, R. C., The number of k-coloured graphs on labelled nodes, Can. J. Math. 12 (1960), 410–414.Google Scholar
6. Read, R. C. and Wright, E. M., Coloured graphs: A correction and extension, Can. J. Math. 22 (1970), 594–596.Google Scholar
7. Robinson, R. W., Enumeration of nonseparable graphs, J. Combinatorial Theor. 9 (1970), 327–356.Google Scholar
8. Wright, E. M., Counting coloured graphs, Can. J. Math. 13 (1961), 683–693.Google Scholar