3-Connected Cores In Random Planar Graphs - Mathematics > CombinatoricsReportar como inadecuado

3-Connected Cores In Random Planar Graphs - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: The study of the structural properties of large random planar graphs hasbecome in recent years a field of intense research in computer science anddiscrete mathematics. Nowadays, a random planar graph is an important andchallenging model for evaluating methods that are developed to study propertiesof random graphs from classes with structural side constraints. In this paperwe focus on the structure of random biconnected planar graphs regarding thesizes of their 3-connected building blocks, which we call cores. In fact, weprove a general theorem regarding random biconnected graphs. If B n is a graphdrawn uniformly at random from a class B of labeled biconnected graphs, then weshow that with probability 1-o1 B n belongs to exactly one of the followingcategories:i Either there is a unique giant core in B n, that is, there is a 0 < c < 1such that the largest core contains ~ cn vertices, and every other corecontains at most n^a vertices, where 0 < a < 1; ii or all cores of B ncontain Olog n vertices.Moreover, we find the critical condition that determines the category towhich B n belongs, and also provide sharp concentration results for the countsof cores of all sizes between 1 and n. As a corollary, we obtain that a randombiconnected planar graph belongs to category i, where in particular c =0.765

. and a = 2-3.

Autor: Nikolaos Fountoulakis, Konstantinos Panagiotou

Fuente: https://arxiv.org/

Documentos relacionados