Random Subgraphs in Cartesian Powers of Regular Graphs

Felix Joos


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 {\rm \ 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 L. Clark, Random subgraphs of certain graph powers, Int. J. Math. Math. Sci., 32(5):285-292, 2002.

Full Text: PDF