On the Rigidity of Sparse Random Graphs
Nati Linial, Jonathan Mosheiff · Journal of Graph Theory · 2016
Abstract A graph with a trivial automorphism group is said to be rigid . Wright proved (Acta Math 126(1) (1971), 1–9) that for a random graph is rigid whp (with high probability). It is not hard to see that this lower bound is sharp and for with positive probability is nontrivial. We show that in the sparser case , it holds whp that G 's 2‐core is rigid. We conclude that for all p , a graph in is reconstructible whp. In addition this yields for a canonical labeling algorithm that almost surely runs in polynomial time with o (1) error rate. This extends the range for which such an algorithm is currently known (T. Czajka and G. Pandurangan, J Discrete Algorithms 6(1) (2008), 85–92).