Geodesic
Counting Coloured Graphs of High Connectivity
Canadian journal of mathematics, Tome 33 (1981) no. 2, pp. 476-484

Voir la notice de l'article provenant de la source Cambridge University Press

Find exact or asymptotic formulae for the number of labelled graphs of order n having a certain property. The property we are interested in in this note is that of being k-coloured and having connectivity at least l. Special cases of this problem have been tackled by many authors; in particular Gilbert [6], Read [9] and Robinson [11] found exact formulae, and Read and Wright [10], and Wright [12], [13] found asymptotic expressions (for many other examples see [7]). Recently Harary and Robinson [8] counted labelled bipartite blocks, that is 2-connected bipartite graphs. (For terms not defined here and general background in graph theory see [1].) Our present investigations have been prompted by [8]; in particular, as a very special case of our results, we shall prove the conjecture published in [8].The exact formulae appearing in the enumeration of labelled graphs in general, and in the enumeration of k-coloured labelled graphs in particular, tend to be very pleasing, especially because of the functional equations relating them. 
Bollobás, Béla. Counting Coloured Graphs of High Connectivity. Canadian journal of mathematics, Tome 33 (1981) no. 2, pp. 476-484. doi: 10.4153/CJM-1981-041-2
@article{10_4153_CJM_1981_041_2,
     author = {Bollob\'as, B\'ela},
     title = {Counting {Coloured} {Graphs} of {High} {Connectivity}},
     journal = {Canadian journal of mathematics},
     pages = {476--484},
     year = {1981},
     volume = {33},
     number = {2},
     doi = {10.4153/CJM-1981-041-2},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1981-041-2/}
}
TY  - JOUR
AU  - Bollobás, Béla
TI  - Counting Coloured Graphs of High Connectivity
JO  - Canadian journal of mathematics
PY  - 1981
SP  - 476
EP  - 484
VL  - 33
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1981-041-2/
DO  - 10.4153/CJM-1981-041-2
ID  - 10_4153_CJM_1981_041_2
ER  - 
%0 Journal Article
%A Bollobás, Béla
%T Counting Coloured Graphs of High Connectivity
%J Canadian journal of mathematics
%D 1981
%P 476-484
%V 33
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1981-041-2/
%R 10.4153/CJM-1981-041-2
%F 10_4153_CJM_1981_041_2

[1] 1. Bollobâs, B., Extremal graph theory (Academic Press, London, New York and San Francisco, 1978). Google Scholar

[2] 2. Bollobâs, B., Graph Theory—An introductory course, Grad. Texts in Math. 63 (Springer-Verlag, New York and Heidelberg, 1979). Google Scholar

[3] 3. Bollobâs, B., Degree sequences of random graphs, Discrete Math. 33 (1981), 1–19. Google Scholar

[4] 4. Bollobâs, B. and Sauer, N., Uniquely colourable graphs wkth large girth, Can. J. Math. 28 (1976), 1340–1344. Google Scholar

[5] 5. Feller, W., An introduction to probability theory and its applications (Wiley and Chapman, New York and London, 1957). Google Scholar

[6] 6. Gilbert, E. N., Enumeration of labelled graphs, Can. J. Math. 8 (1956), 405–411. Google Scholar

[7] 7. Harary, F. and Palmer, E. M., Graphical enumeration (Academic Press, New York, 1973). Google Scholar

[8] 8. Harary, F. and Robinson, W., Labelled bipartite blocks, Can. J. Math. 31 (1979), 60–68. Google Scholar

[9] 9. Read, R. C., The number of coloured graphs on labelled nodes, Can. J. Math. 12 (1960), 410–414. Google Scholar

[10] 10. Read, R. C. and Wright, E. M., Coloured graphs: A correction and extension, Can. J. Math. 22 (1970), 594–596. Google Scholar

[11] 11. Robinson, R. W., Enumeration of non-separable graphs, J. Combinatorial Theory 9 (1970), 327–356. Google Scholar

[12] 12. Wright, E. M., Counting coloured graphs, Can. J. Math. 13 (1961), 683–693. Google Scholar

[13] 13. Wright, E. M., Counting coloured graphs II, Can. J. Math. 16 (1964), 128–135. Google Scholar

Cité par Sources :