On the diameter of random planar graphs
Résumé
We show that the diameter D(G_n) of a random (unembedded) labelled connected planar graph with n vertices is asymptotically almost surely of order n^{1/4} , in the sense that there exists a constant c > 0 such that P (D(G_n ) ∈ (n^{1/4−e} , n^{1/4+e} )) ≥ 1 − exp(−nc(e) ) for e small enough and n large enough (n ≥ n0 (e)). We prove similar statements for rooted 2-connected and 3-connected embedded (maps) and unembedded planar graphs.
Domaines
Combinatoire [math.CO]
Origine : Fichiers produits par l'(les) auteur(s)