On the Rigidity of Sparse Random Graphs. Issue 2 (15th July 2016)

• Record Type: Journal Article
• Authors: Linial, Nati; Mosheiff, Jonathan
• Is Part Of: Journal of graph theory. Volume 85:Issue 2(2017)
• Page Start: 466
• Page End: 480
• Publication Date: 2016-07-15
• Subjects: core -- sparse random graph -- rigidity -- reconstruction -- graph canonical labeling; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22073
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A graph with a trivial automorphism group is said to be rigid . Wright proved (Acta Math 126(1) (1971), 1–9) that for log n n + ω ( 1 n ) ≤ p ≤ 1 2 a random graph G ∈ G ( n, p ) is rigid whp (with high probability). It is not hard to see that this lower bound is sharp and for p < ( 1 − ε ) log n n with positive probability aut ( G ) is nontrivial. We show that in the sparser case ω ( 1 n ) ≤ p ≤ log n n + ω ( 1 n ), it holds whp that G 's 2‐core is rigid. We conclude that for all p, a graph in G ( n, p ) is reconstructible whp. In addition this yields for ω ( 1 n ) ≤ p ≤ 1 2 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).