Mathematics – Combinatorics
Scientific paper
2009-07-02
Mathematics
Combinatorics
Scientific paper
Consider a family $\mathcal{T}$ of 3-connected graphs of moderate growth, 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, which generalizes previously studied cases such as planar graphs and series-parallel graphs. We provide a general result 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, which are either normal or Poisson, for several basic parameters, including the number of edges, number of blocks and number of components. For the size of the largest block we find a fundamental dichotomy: classes similar to planar graphs have almost surely a unique block of linear size, while classes similar to series-parallel graphs have only sublinear blocks. This dichotomy also applies to the size of the largest 3-connected component. For some classes under study both regimes occur, because of a critical phenomenon as the edge density in the class varies.
Gimenez Omer
Noy Marc
Rué Juanjo
No associations
LandOfFree
Graph classes with given 3-connected components: asymptotic enumeration and random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Graph classes with given 3-connected components: asymptotic enumeration and random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph classes with given 3-connected components: asymptotic enumeration and random graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-730779