Premium
Random unlabelled graphs containing few disjoint cycles
Author(s) -
Kang Mihyun,
McDiarmid Colin
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20355
Subject(s) - combinatorics , mathematics , disjoint sets , cograph , discrete mathematics , vertex (graph theory) , random graph , limiting , graph , indifference graph , pairwise comparison , chordal graph , 1 planar graph , statistics , mechanical engineering , engineering
We call a set B of vertices in a graph G a blocker if the graph G ‐ B obtained from G by deleting the vertices in B has no cycles. The classical Erdős‐Pósa theorem (1965) states that for each positive integer k there is a positive integer f ( k ) such that in each graph G which contains at most k pairwise vertex‐disjoint cycles, there is a blocker B of size at most f ( k ). We show that, amongst all unlabelled n ‐vertex graphs with at most k disjoint cycles, all but an exponentially small proportion have a unique blocker of size k . We also determine the asymptotic number and properties of such graphs. For example we study the limiting probability that such graphs are connected, the limiting average number of vertices not in the giant component, and the limiting distribution of the chromatic number. Further, we give more detailed results concerning graphs with no two disjoint cycles. These results complement recent results for labelled graphs by Kurauskas and the second author. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011