2022/02/07 by Adhikari, Kartick, Chakraborty, Sukrit
#05C80 #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2202.02968
In a recent work, Huang and Tikhomirov considered the shotgun assembly for Erd\H os-Rényi graphs \mathcal G(n,pn) with pn=n-α, and showed that the graph is reconstructable if 0<α< (1)/(2) and not reconstructable if (1)/(2)<α<1 from its 1-neighbourhoods. In this article, we consider random geometric graphs G(n,r), where r2=n-α and 0<α<1, on flat torus. Interestingly, unlike the results for the Erd\H os-Rényi random graphs, we show that the random geometric graph is always reconstructable from its 1-neighbourhoods.