Forbidden subgraphs in connected graphs

Given a set xi = {H-1, H-2,...} of connected non-acyclic graphs, a xi-free graph is one which does not contain any member of as copy. Define the excess of a graph as the difference between its number of edges and its number of vertices. Let (W) over cap (k,xi) be the exponential generating function (EGF for brief) of connected xi-free graphs of excess equal to k (k greater than or equal to 1). For each fixed, a fundamental differential recurrence satisfied by the EGFs (W) over cap (k,xi) is derived. We give methods on how to solve this nonlinear recurrence for the first few values of k by means of graph surgery. We also show that for any finite collection xi of non-acyclic graphs, the EGFs (W) over cap (k,xi) are always rational functions of the generating function, T, of Cayley's rooted (non-planar) labelled trees. From this, we prove that almost all connected graphs with n nodes and n + k edges are xi-free, whenever k = o(n(1/3)) and \xi\ < infinity by means of Wright's inequalities and saddle point method. Limiting distributions are derived for sparse connected xi-free components that are present when a random graph on n nodes has approximately n/2 edges. In particular, the probability distribution that it consists of trees, unicyclic components,...,(q + 1)-cyclic components all xi-free is derived. Similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed. (C) 2003 Elsevier B.V. All rights reserved.