Some remarks on sparsely connected isomorphism-free labeled graphs (Q4508360)

The authors say that a graph \(G\) with \(n\) vertices and \(m\) edges is \((q+1)\)-cyclic, where \(q\geq 0\), if \(G\) is connected and \(m= n+q\). Let \(C\) denote a finite collection of graphs each of which is \((q+1)\)-cyclic for some \(q\geq 0\) (but not necessarily the same \(q\) for each graph). The authors derive an asymptotic expression for the probability that a random graph with \(n\) vertices and \({1\over 2} n+O(n^{1/3})\) edges has a specified number of components that are \((q+1)\)-cyclic for \(0\leq q\leq k\), no components that are \((q+1)\)-cyclic for \(q>k\), and no components that contain any members of \(C\) as an induced subgraph. They also show, among other things, that almost all connected graphs with \(n\) vertices and \(n+ o(n^{1/3})\) edges contain no members of \(C\) as an induced subgraph. For the entire collection see [Zbl 0935.00049].