Forbidden subgraphs in connected graphs

AbstractGiven a set ξ={H1,H2,…} of connected non-acyclic graphs, a ξ-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 Wk,ξ be the exponential generating function (EGF for brief) of connected ξ-free graphs of excess equal to k(k⩾1). For each fixed ξ, a fundamental differential recurrence satisfied by the EGFs Wk,ξ 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 ξ of non-acyclic graphs, the EGFs Wk,ξ 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 ξ-free, whenever k=o(n1/3) and |ξ|<∞ by means of Wright's inequalities and saddle point method. Limiting distributions are derived for sparse connected ξ-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 ξ-free is derived. Similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed