Random subgraphs in Cartesian powers of regular graphs
Summary: Let \(G\) be a connected \(d\)-regular graph with \(k\) vertices. We investigate the behaviour of a spanning random subgraph \(G^n_p\) of \(G^n\), the \(n\)-th Cartesian power of \(G\), which is constructed by deleting each edge independently with probability \(1-p\). We prove that \(\lim\limits_{n \rightarrow \infty} \mathbb{P}[G^n_p \text{\;is \;connected}]=e^{-\lambda}\), if \(p=p(n)=1-\left(\frac{\lambda_n^{1/n}}{k}\right)^{1/d}\) and \(\lambda_n \rightarrow \lambda>0\) as \(n \rightarrow \infty\). This extends a result of \textit{L. Clark} [``Random subgraphs of certain graph powers, Int. J. Math. Math. Sci. 32, No. 5, 285--292 (2002; Zbl 1004.05054)].
- Random subgraphs of certain graph powers
- scientific article; zbMATH DE number 3869382
- Regular subgraphs of random graphs
- Random graphs and their subgraphs
- Subgraphs of Random Graphs
- Distribution of subgraphs of random regular graphs
- On random subgraphs of Kneser and Schrijver graphs
- scientific article; zbMATH DE number 3943865
- Subgraphs in non-uniform random hypergraphs
- On Subgraph Sizes in Random Graphs
This page was built for publication: Random subgraphs in Cartesian powers of regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426814)
