# different way of selecting a random graph

Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this type of random graph been studied before (i realise the output highly depends on what graph you start with).

• This is the setup for "site percolation" on G, and there's a substantial literature. See some of the references at en.wikipedia.org/wiki/Percolation_theory
– j.c.
Jun 25 '14 at 21:12
• You may wish to read this.
– Bach
Jun 26 '14 at 8:54

There are at least two instances that I can recall where such graphs have been studied. As you've remarked, in general too much depends on the base graph, so you're only going to get somewhere by restricting to reasonable choices of base graph: for instance the complete graph on $n$-vertices is an awful choice for the base since you already know everything about any "random" induced subgraph just by knowing how many vertices it contains.
With that out of the way, here are two examples -- both involve sufficient conditions for the presence of giant components a.a.s (a la Erdos-Renyi). The first case of base graph is the Cayley graph of the symmetric group $S_n$ where generators are restricted to transpositions. See the paper
The main result involves sufficient conditions for the presence of a giant component. Similarly, if you change the base graph to (the 1-skeleton of) a product of $n$-dimensional cubes $Q^n$, then consider the paper: