The Degree Sequence of Random Graphs from Subcritical Classes

Authors:

Abstract
In this work we determine the expected number of vertices of degreek=k(n) in a graph withnvertices that is drawn uniformly at random from asubcritical graph class. Examples of such classes are outerplanar, series-parallel, cactus and clique graphs. Moreover, we provide exponentially small bounds for the probability that the quantities in question deviate from their expected values.

This publication has 13 references indexed in Scilit: