Connectivity of Random Cubic Sum Graphs
Published in SIAM Journal on Discrete Mathematics, 2010
A. Beveridge, Connectivity of Random Cubic Sum Graphs, SIAM Journal on Discrete Mathematics, Vol. 24, Issue 3 (2010), 895-909.
Preprint link: https://github.com/mathbeveridge/mathbeveridge.github.io/blob/master/files/randsumgraph.pdf
Choose each element of $\mathbb{Z}_2^d$ independently with probability $p$. Then construct the graph such that there is an edge between $a$ and $b$ if and only if vertex $a+b$ also appears in the graph. We determine threshold functions for various properties of this random graph, including connectivity.