Some remarks on sparsely connected isomorphism-free labeled graphs
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].
- The asymptotic number of labeled connected graphs with a given number of vertices and edges
- A common asymptotic behavior for different classes of sparse labelled graphs with given number of vertices and edges
- scientific article; zbMATH DE number 3916307
- scientific article; zbMATH DE number 4075100
- Forbidden subgraphs in connected graphs
This page was built for publication: Some remarks on sparsely connected isomorphism-free labeled graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508360)
