Forbidden Subgraphs in Connected Graphs

Forbidden Subgraphs in Connected Graphs
Vlady Ravelomanana

Given a set xi={H_1,H_2,..} of connected non acyclic graphs, a xi-free graph is
a graph which does not contain any member of xi as a copy. Define the excess of a graph
as the difference between its number of edges and its numbers of vertices. Let \widehat{W}_{k,\xi}
be the exponential generating function (EGF) of connected $xi$-free graphs of excess $k\ge 1$.
For any fixed $\xi$, we derive a fundamental differential recurrence satisfied by the EGFs
$\widehat{W}_{k,\xi}$. We give methods for solving this non-linear recurrence for the first
few values of $k$ by means of graph surgery. It is also shown that, for any finite collection
xi of non-acyclic graphs, the EGFs \widehat{W}_{k,xi} are always rational functions of
the generating function $T$ of Cayley's rooted (non-planar) labelled trees. Whence 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|<infty, by means of Wright's inequalities and the saddle point
method. Limiting distribution 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 that the graph consists of trees, unicyclic components, ..., (q+1)-cyclic
components is derived. Similar results are also given for multigraphs.