The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Graph classes with given 3-connected components: asymptotic counting and critical phenomena

Noy, M (Catalunya)
Monday 07 April 2008, 16:30-17:15

Seminar Room 1, Newton Institute


Fix a family T of 3-connected labelled graphs with moderate growth, and let G be the class of graphs whose 3-connected components are the graphs in T. We present a general framework for analyzing such graph classes based on singularity analysis of generating functions. This generalizes previously studied cases such as planar graphs and series-parallel graphs. There are two main regimes, that we call tree-like and map-like. In the tree-like case the largest 2-connected and 3-connected cores are almost surely of constant size, whereas in the map-like case they are of linear size. For some of the classes under study we show the presence of critical phenomena as the edge density in the class varies.


[pdf ]




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧