๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The Distribution of the Maximum Vertex Degree in Random Planar Maps

โœ Scribed by Zhicheng Gao; Nicholas C. Wormald

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
297 KB
Volume
89
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

โœฆ Synopsis

We determine the limiting distribution of the maximum vertex degree 2 n in a random triangulation of an n-gon, and show that it is the same as that of the maximum of n independent identically distributed random variables G 2 , where G 2 is the sum of two independent geometric(1ร‚2) random variables. This answers affirmatively a question of Devroye, Flajolet, Hurtado, Noy and Steiger, who gave much weaker almost sure bounds on 2 n . An interesting consequence of this is that the asymptotic probability that a random triangulation has a unique vertex with maximum degree is about 0.72. We also give an analogous result for random planar maps in general.

๐Ÿ“œ SIMILAR VOLUMES

A Pattern of Asymptotic Vertex Valency D
A Pattern of Asymptotic Vertex Valency Distributions in Planar Maps
โœ Valery A Liskovets ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 159 KB

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 show

Asymptotic Normality of the Vertex Degre
Asymptotic Normality of the Vertex Degree in Random Subgraphs of the n-Cube
โœ Urszula Konieczna ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 245 KB

We consider two types of random subgraphs of the n-cube. For these models we study the asymptotic behaviour of the number of vertices of degree d.

The distribution of nodes of given degre
The distribution of nodes of given degree in random trees
โœ Drmota, Michael; Gittenberger, Bernhard ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 391 KB ๐Ÿ‘ 2 views

Let T n denote the set of unrooted unlabeled trees of size n and let k โ‰ฅ 1 be given. By assuming that every tree of T n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value โˆผ ยต k n and variance โˆผ ฯƒ 2 k n with positive constants ยต

Structural Properties of Planar Maps wit
Structural Properties of Planar Maps with the Minimal Degree 5
โœ Oleg Borodin ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 371 KB

## Abstract We improve some old results concerning the numbers of such edges and faces in planar graphs having minimal degree 5 which are incident only to vertices of minor degrees.

The linear arboricity of planar graphs o
The linear arboricity of planar graphs of maximum degree seven is four
โœ Jian-Liang Wu; Yu-Wen Wu ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 130 KB ๐Ÿ‘ 2 views

## Abstract The linear arboricity of a graph __G__ is the minimum number of linear forests which partition the edges of __G__. Akiyama et al. conjectured that $\lceil {\Delta {({G})}\over {2}}\rceil \leq {la}({G}) \leq \lceil {\Delta({G})+{1}\over {2}}\rceil$ for any simple graph __G__. Wu wu prove