Forbidden subgraphs in connected graphs (Q1884919): Difference between revisions

Let \(H\) denote a finite collection of connected non-acyclic graphs. The authors obtain a differential recurrence relation satisfied by the exponential generating functions that enumerate connected non-acyclic \(H\)-free labelled graphs with \(k\) more edges than vertices. These relations are complicated, in general, but the authors show that they can lead to forms for the generating functions in terms of a frequently-encountered tree polynomial. They then discuss how to exploit this fact in order to conclude, for example, that if \(k= o(n^{1/3})\), then almost all connected labelled graphs with \(n\) vertices and \(n+ k\) edges are \(H\)-free. They also give results on the limiting probability that a random labelled graph with \(n\) vertices and \(n/2+ O(n^{1/3})\) edges contains copies of certain specified graphs but does not contain copies of others.