Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653219 | European Journal of Combinatorics | 2016 | 11 Pages |
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))logn/loglogn blocks, and each path passes through at most 5(nlogn)1/2 blocks. These results extend to 'weakly block-stable' classes of graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Colin McDiarmid, Alex Scott,