The enumeration of zero-one matrices with nonzero row and column sums has recently been solved in the context of certain problems arising in architectural design. However, this solution took no account of the symmetries of these configurations, which would be required for any realistic application in an architectural context. In graph-theoretic terms, this new problem calls for counting unlabelled bicoloured graphs with no isolated points. We determine these numbers by deriving their generating function. We also present an equivalent set of recurrence relations, from which the numbers may be easily computed.
Get full access to this article
View all access options for this article.
References
1.
AlexanderCManheimM L, 1962“The use of diagrams in highway route location: an experiment” R62–3, Civil Engineering Systems Laboratory, Cambridge, Mass
2.
AlexanderC, 1964Notes on the Synthesis of Form (Harvard University Press, Cambridge, Mass)
3.
AtkinR H, 1974a“An approach to structure in architectural and urban design. 1. Introduction and mathematical theory”Environment and Planning B151–67
4.
AtkinR H, 1974b“An approach to structure in architectural and urban design. 2. Algebraic representation and local structure”Environment and Planning B1173–191
5.
AtkinR H, 1975“An approach to structure in architectural and urban design. 3. Illustrative examples”Environment and Planning B221–57
6.
BattyM, 1974“A theory of Markovian design machines”Environment and Planning B1125–146
7.
BolkerE DCrapoH, 1977“How to brace a one-story building”Environment and Planning B4125–152
8.
BondyJ AMurtyU S R, 1976Graph Theory and Applications (Macmillan, London)
9.
CrapoH, 1977“More on the bracing of one-story buildings”Environment and Planning B4153–156
10.
EarlC F, 1977“A note on the generation of rectangular dissections”Environment and Planning B4241–246
11.
FawcettW H, 1976a“Measuring adaptability”Translations of the Martin Centre (Woodhead-Faulkner, Cambridge) 15–40
12.
FawcettW H, 1976b“School management and school design”Journal of Architectural Research5 (3) 10–21
13.
FawcettW H, 1977“Activity-space systems: Four isomorphisms”Environment and Planning B431–36
14.
HararyF, 1958“On the number of bicolored graphs”Pacific Journal of Mathematics8743–755
15.
HararyF, 1969Graph Theory (Addison-Wesley, Reading, Mass)
16.
HararyFNormanR ZCartwrightD, 1965Structural Models: An Introduction to the Theory of Directed Graph (John Wiley, New York)
17.
HararyFPalmerE M, 1973Graphical Enumeration (Academic Press, New York)
18.
HararyFPrinsG, 1963“Enumeration of bicolorable graphs”Canadian Journal of Mathematics15237–248
19.
HararyFReadR C, 1974“Is the null graph a pointless concept?” in Graphs and Combinatorics Eds BariRHararyF (Springer, Berlin) pp 37–44
20.
JacksonD M, 1976“The enumeration of spanning zero-one matrices”Environment and Planning B375–78
21.
KronG, 1963Diakoptics (Macdonald, London)
22.
MarchL, 1976“A Boolean description of a class of built forms” in The Architecture of Form Ed. MarchL (Cambridge University Press, London) pp 41–73
23.
MatelaRO'HareE, 1976“Graph-theoretic aspects of polyominoes and related spatial structures”Environment and Planning B379–110
24.
MitchellW JSteadmanJ PLiggettR S, 1976“Synthesis and optimization of small rectangular floor plans”Environment and Planning B337–70
25.
OnaderaR, 1973“On the number of trees in a complete n-partite graph”The Matrix and Tensor Quarterly23(4)
26.
OnaderaRSaishuKFukujnM, 1977“On labelled diakoptical graphs”The Matrix and Tensor Quarterly28(2)
27.
ReadR C, 1960“The number of k-coloured graphs on labelled nodes”Canadian Journal of Mathematics12410–414
28.
RobinsonR W, 1968“Enumeration of colored graphs”Journal of Combinatorial Theory4181–190
29.
SteadmanJ P, 1973“Graph theoretic representation of architectural arrangement”Architectural Research and Teaching2/3161–172; reprinted, 1976, in The Architecture of Form Ed. MarchL (Cambridge University Press, London) pp 94–115
