Random Subgraphs in Sparse Graphs

Abstract

We investigate the threshold probability for connectivity of sparse graphs under weak assumptions. As a corollary this completely solve the problem for Cartesian powers of arbitrary graphs. In detail, let $G$ be a connected graph on $k$ vertices, $G^n$ the $n$-th Cartesian power of $G$, ${\alpha }_i$ be the number of vertices of degree $i$ of $G$, $\lambda$ be a positive real number, and $G_p^n$ be the graph obtained from $G^n$ by deleting every edge independently with probability $1-p$. If ${\sum }_i{\alpha }_i(1-p{)}^i={\lambda }^{\frac{1}{n}}$, then ${\lim }_{n\to \infty }\mathbb{P}[G_p^n\mathrm{is}\mathrm{connected}]=\exp (-\lambda )$. This result extends known results for regular graphs. The main result implies that the threshold probability does not depend on the graph structure of $G$ itself, but only on the degree sequence of the graph.

14 pages

Cited by in corpus (1)

• Connectivity Threshold for random subgraphs of the Hamming graph