Statistics of planar graphs viewed from a vertex: A study via labeled trees

Abstract

We study the statistics of edges and vertices in the vicinity of a reference vertex (origin) within random planar quadrangulations and Eulerian triangulations. Exact generating functions are obtained for theses graphs with fixed numbers of edges and vertices at given geodesic distances from the origin. Our analysis relies on bijections with labeled trees, in which the labels encode the information on the geodesic distance from the origin. In the case of infinitely large graphs, we give in particular explicit formulas for the probabilities that the origin have given numbers of neighboring edges and/or vertices, as well as explicit values for the corresponding moments.

36 pages, 15 figures, tex, harvmac, epsf

References in corpus (4)

• Geodesic Distance in Planar Graphs
• Census of Planar Maps: From the One-Matrix Model Solution to a Combinatorial Proof
• Random trees between two walls: Exact partition function
• Counting Colored Random Triangulations

Cited by in corpus (8)

• Complex Networks on Hyperbolic Surfaces
• Limit of normalized quadrangulations: The Brownian map
• Random trees between two walls: Exact partition function
• Combinatorics of bicubic maps with hard particles
• Integrability of graph combinatorics via random walks and heaps of dimers
• An invariance principle for conditioned trees
• Planar maps and random partitions
• The vertical profile of embedded trees