Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-12-01T04:23:11.926Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic properties of rooted 3-connected maps on surfaces

Part of: Graph theory

Published online by Cambridge University Press:  09 April 2009

Edward A. Bender ,
Zhicheng Gao ,
L. Bruce Richmond  and
Nicholas C. Wormald
Edward A. Bender
Affiliation:
Center for Communications Research4350 Executive Drive San Diego, CA 92121, USA
Zhicheng Gao
Affiliation:
Department of Combinatorics and OptimizationUniversity of Waterloo Waterloo, Ontario N2L3G1, Canada
L. Bruce Richmond
Affiliation:
Department of Combinatorics and OptimizationUniversity of WaterlooWaterloo, Ontario N2L3G1, Canada
Nicholas C. Wormald
Affiliation:
Department of MathematicsUniversity of MelbourneParkville, VIC 3052Australia e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

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 obtain asymptotics for the number of rooted 3-connected maps on an arbitrary surface and use them to prove that almost all rooted 3-connected maps on any fixed surface have large edge-width and large face-width. It then follows from the result of Roberston and Vitray [10] that almost all rooted 3-connected maps on any fixed surface are minimum genus embeddings and their underlying graphs are uniquely embeddable on the surface.

MSC classification

Secondary: 05C10: Planar graphs; geometric and topological aspects of graph theory 05C30: Enumeration in graph theory 05C15: Coloring of graphs and hypergraphs
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 60 , Issue 1 , February 1996 , pp. 31 - 41
Copyright
Copyright © Australian Mathematical Society 1996

References

[1]Bender, E. A. and Canfield, E. R., ‘The asymptotic number of rooted maps on a surface’, J. Combin. Theory Ser. A 43 (1986), 244–257.CrossRefGoogle Scholar
[2]Bender, E. A., Canfield, E. R. and Robinson, R. W., ‘The enumeration of maps on the torus and projective plane’, Canad. Math. Bull. 31 (1988), 257–271.CrossRefGoogle Scholar
[3]Bender, E. A., Gao, Z. C. and Richmond, L. B., ‘Submaps of maps I: general 0–1 laws’, J. Combin. Theory Ser. B 55 (1992), 104–117.CrossRefGoogle Scholar
[4]Bender, E. A., Gao, Z. C. and Richmond, L. B., ‘Almost all rooted maps have large representativities’, J. Graph Theory 18 (1994), 545–555.CrossRefGoogle Scholar
[5]Bender, E. A. and Wormald, N. C., ‘The asymptotic number of rooted nonseparable maps on a surface’, J. Combin. Theory Ser. A 49 (1988), 370–380.CrossRefGoogle Scholar
[6]Brown, W. G., ‘Enumeration of quadrangular dissections of the disk’, Canad. J. Math. 17 (1965), 302–317.CrossRefGoogle Scholar
[7]Gao, Z. C., ‘A pattern for the asymptotic number of rooted maps on surfaces’, J. Combin. Theory Ser. A 64 (1993), 246–264.CrossRefGoogle Scholar
[8]Mullin, R. C. and Schellenberg, P. J., ‘The enumeration of c-nets via quadrangulations’, J. Combin. Theory 4 (1968), 259–276.CrossRefGoogle Scholar
[9]Richmond, L. B. and Wormald, N. C., ‘Random triangulations of the plane’, European J. Combin. 9 (1988), 61–71.CrossRefGoogle Scholar
[10]Robertson, N. and Vitray, R., ‘Representativity of surface embeddings’, Algorithms Combin. 9 (1990), 293–328.Google Scholar
[11]Tutte, W. T., ‘A theory of 3-connected graphs’, Nederl. Akad. Wetensch. Proc. Ser. B 64 (1961), 441–455.CrossRefGoogle Scholar
[12]Tutte, W. T., ‘A census of planar maps’, Canad. J. Math. 15 (1963), 249–271.CrossRefGoogle Scholar
[13]Whitney, H., ‘Congruent graphs and the connectivity of graphs’, Amer.J. Math. 54 (1932), 150–168.CrossRefGoogle Scholar
[14]Wormald, N. C., ‘Enumeration of labelled graphs I: 3-connected graphs’, J. London Math. Soc. (2) 19 (1979), 7–12.CrossRefGoogle Scholar