A Pattern of Asymptotic Vertex Valency Distributions in Planar Maps

✍ Scribed by Valery A Liskovets

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 159 KB
• Volume: 75
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1998.1870

✦ Synopsis

Let a vertex be selected at random in a set of n-edged rooted planar maps and p k denote the limit probability (as n Ä ) of this vertex to be of valency k. For diverse classes of maps including Eulerian, arbitrary, polyhedral, and loopless maps as well as 2-and 3-connected triangulations, it is shown that non-zero p k behave asymptotically in a uniform manner: p k tc (?k) &1Â2 r k as k Ä with some constants r and c depending on the class. This distribution pattern can be reformulated in terms of the root vertex valency. By contrast, p k =2 &k for the class of arbitrary plane trees and p k =(k&1) 2 &k for triangular dissections of convex polygons.