Given set zeta = (H_1, H_2, ---) of connected non-acyclic graphs, a zeta-free graph is one which does not ocntain any member of zeta as induced subgraphs. Our first purpose in this paper is to perform an investigation into the limiting distribution of labeled graphs and multigraphs (graphs with possible self-loops nd multiple edges), with n vertices and approximately 1/2n edges, in which all sparse connected components are zeta-free. Next, we prove that for any finite collection zeta of multicyclic graphs almost all connected graphs with n vertices and n + o(n~1/3) edges are zeta-free. The same result holds for multigraphs.
展开▼
