On the r-diameters of random graphs in the Bollobas-Riordan model

This work is concerned with the Bollobas-Riordan model of a random web graph. This model is good for describing the behaviour of the real WWW. We consider a generalization of the notion of the diameter of a graph - the so-called r-diameter which is defined as a maximum value taken over all sets of vertices of size r of a minimum distance between a pair of vertices in a given set. We prove a theorem which states that a web graph on n vertices is almost sure to have the r-diameter as close presumed to the value Ln n-lnr/lnlnn.