Random graphs from a block-stable class
Authors:
- Colin McDiarmidCMColin McDiarmid
- Alex ScottASAlex Scott
Preprint
Abstract
A class of graphs is called block-stable when a graph is in the class if and only if each of its blocks is. We show that, as for trees, for most $n$-vertex graphs in such a class, each vertex is in at most $(1+o(1)) \log n / \log\log n$ blocks, and each path passes through at most $5 (n \log n)^{1/2}$ blocks. These results extend to `weakly block-stable' classes of graphs.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Maximum degree in minor-closed classes of graphsEuropean Journal of Combinatorics, 2016
- On the connectivity of random graphs from addable classesJournal of Combinatorial Theory, Series B, 2013
- The Degree Sequence of Random Graphs from Subcritical ClassesCombinatorics, Probability and Computing, 2009
- Random Graphs from a Minor-Closed ClassCombinatorics, Probability and Computing, 2009
- On the Maximum Degree of a Random Planar GraphCombinatorics, Probability and Computing, 2008
- Graph classes with given 3-connected components: asymptotic counting and critical phenomenaElectronic Notes in Discrete Mathematics, 2007
- Random planar graphsJournal of Combinatorial Theory, Series B, 2005
- A Course in Combinatorics2001
- The maximum degree in a random tree and related problemsRandom Structures & Algorithms, 1994
- The average height of binary trees and other simple treesJournal of Computer and System Sciences, 1982