Loading...
Loading...

Go to the content (press return)

Graph classes with given 3-connected components: asymptotic enumeration and random graphs

Author
Giménez, O.; Noy, M.; Rue, J.
Type of activity
Journal article
Journal
Random structures and algorithms
Date of publication
2013
Volume
42
Number
4
First page
438
Last page
479
DOI
https://doi.org/10.1002/rsa.20421 Open in new window
URL
http://onlinelibrary.wiley.com/doi/10.1002/rsa.20421/abstract Open in new window
Abstract
Consider a family equation image of 3-connected graphs of moderate growth, and let equation image be the class of graphs whose 3-connected components are graphs in equation image. 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 equation image, based on the singulariti...
Keywords
asymptotic enumeration, graph minors, graph parameters, planar graphs
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants