Shotgun Assembly of Random Geometric Graphs

Authors Kartick Adhikari, Sukrit Chakraborty

Publication date 7 February 2022

Random graphs (graph-theoretic aspects) (05C80)

Abstract: In a recent work, Huang and Tikhomirov considered the shotgun assembly for ErdH os-R'enyi graphs

m a t h c a l G (n, p_{n})

with

p_{n} = n^{- a l p h a}

, and showed that the graph is reconstructable if

0 < a l p h a < f r a c 12

and not reconstructable if

f r a c 12 < a l p h a < 1

from its

1

-neighbourhoods. In this article, we consider random geometric graphs

G (n, r)

, where

r^{2} = n^{- a l p h a}

and

0 < a l p h a < 1

, on flat torus. Interestingly, unlike the results for the ErdH os-R'enyi random graphs, we show that the random geometric graph is always reconstructable from its 1-neighbourhoods.

This page was built for publication: Shotgun Assembly of Random Geometric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6390335)