MASCOTTE no longer exists => visit the new COATI project-team
 


Seminaire MASCOTTE
Families of graphs defined by their 3-connected components: universal behavior, enumeration and limit laws

par Juanjo Rué Perna


Date :18/06/08
Location :Lagrange Gris


Consider a family $\mathcal{T}$ of $3$-connected graphs, and let $\mathcal{G}$ be the class of graphs whose $3$-connected components are graphs in $\mathcal{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 series-parallel graphs. We provide a general theorem for the asymptotic number of graphs in $\mathcal{G}$, based on the singularities of the exponential generating function associated to $\mathcal{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.

This is joint work with Omer Giménez and Marc Noy.



Page des séminaires