|
Title:
|
Graph classes with given 3-connected components: asymptotic counting, limit laws and critical phenomena
|
|
Author:
|
Giménez Llach, Omer; Noy Serrano, Marcos; Rué Perna, Juan José
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics |
|
Abstract:
|
Consider a family T of 3-connected graphs, and let G be the class of graphs whose 3-connected components are graphs in T . We present a general framework for analyzing such graphs classes based on singularity analysis of generating functions. This generalizes previously studied cases such as planar graphs and seriesparallel graphs. We provide a general theorem for the asymptotic number of graphs in G, based on the singularities of the exponential generating function associated to T . We derive limit laws for the number of connected components, for the number of edges and for the number of 2-connected components. At last, for some classes under study we show the existence of critical phenomena as the edge density in the class varies. |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística
-Combinatorial analysis
-Graph theory
-analytic combinatorics
-asymptotic enumeration
-limit laws
-random graph
-planar graph
-Grafs, Teoria de
-Anàlisi combinatòria |
|
Rights:
|
|
|
Document type:
|
Article - Submitted version
Conference Object |
|
Published by:
|
Edicions de la Universitat de Lleida (UdL)
|
|
Share:
|
|
