Random graphs from a block class

Authors:
  • CMColin McDiarmid
    Colin McDiarmid
  • ASAlex Scott
    Alex Scott

Abstract
A block class is a class of graphs such that a graph is in the class if and only if each of its blocks is. We show that, as for trees, for most random 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. Further, these results remain true when we condition on the numbers of components and blocks, and on the list of blocks appearing; and if there are at most k blocks (where k=k(n) tends to infinity) we may replace n by k to obtain improved bounds.

This publication has 12 references indexed in Scilit: