Forbidden Subgraphs in Connected Graphs

Original · EN

Given a set ξ={H₁,H₂,...} 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 Wₖ,ξ be theexponential 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 Wₖ,ξ 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 Wₖ,ξ 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(n¹/³) 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.