In this work we determine the expected number of vertices of degree k = k(n) in a graph with n vertices that is drawn uniformly at random from a subcritical 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.
['Nicla Bernasconi', 'Konstantinos Panagiotou', 'Angelika Steger']
The degree sequence of random graphs from subcritical classes