In this paper we study d-dependent random graphs -- introduced by Brody and Sanchez -- which are the family of random graph distributions where each edge is present with probability p, and each edge is independent of all but at most d other edges. For this random graph model, we analyze degree sequences, jumbledness, connectivity, and subgraph containment. Our results mirror those of the classical Erd{o}s--R\'enyi random graph, which are recovered by specializing our problem to $d=0$, although we show that in many regards our setting is appreciably more nuanced. We survey what is known for this model and conclude with a variety of open questions.
No takes yet. Share an insight, caveat, or question.
Brody et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: