Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: The Number of Labeled 2-Connected Planar Graphs | The Number of Labeled 2-Connected Planar Graphs Edward A. Bender Department of Mathematics University of California at San Diego La Jolla CA 92093-0112 USA ebender@ Zhicheng Gao School of Mathematics and Statistics Carleton University Ottawa K1S 5B6 Canada zgao@ Nicholas C. Wormald Department of Mathematics and Statistics University of Melbourne VIC 3010 Australia nick@ Submitted April 9 2001 Revised November 3 2002 Accepted November 10 2002. MR Subject Classifications 05C30 05A16 Abstract We derive the asymptotic expression for the number of labeled 2-connected planar graphs with respect to vertices and edges. We also show that almost all such graphs with n vertices contain many copies of any fixed planar graph and this implies that almost all such graphs have large automorphism groups. Research supported by the Australian Research Council and NSERC 1 Research supported by the Australian Research Council THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 R43 1 1 Introduction A planar map is a connected graph embedded in the sphere. A planar graph is a connected graph which can be embedded in the sphere. Throughout the paper unless stated otherwise all planar maps and graphs have no loops or multiple edges. Since a single graph may have many embeddings there are generally fewer planar graphs than there are maps. In this paper we study the number of labeled 2-connected planar graphs with a given number of vertices and edges. Symmetry causes difficulties in the enumeration of both graphs and maps. In graphical enumeration one destroys symmetry by labeling the vertices. In map enumeration it is simpler to destroy symmetry by a Tutte rooting select an edge a direction on the edge and a side of the edge. In enumerating c-connected graphs or maps it is natural to proceed from 1-connected to 2-connected and thence to 3-connected by means of functional compositions based on theorems about graphical construction. This scheme has not yet
