On the Rigidity of Sparse Random Graphs

DOI10.1002/jgt.22073zbMath1375.05249arXiv1505.01189OpenAlexW2285869554MaRDI QIDQ5272929

Nathan Linial, Jonathan Mosheiff

Publication date: 5 July 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.01189

zbMATH Keywords

rigiditycorereconstructionsparse random graphgraph canonical labeling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Related Items (1)

The Threshold of Symmetry in Random Graphs with Specified Degree Sequences

Cites Work

• A congruence theorem for trees
• Improved random graph isomorphism
• Graphs on unlabelled nodes with a given number of edges
• The number of trees
• Almost every graph has reconstruction number three
• Random Graph Isomorphism
• On tree census and the giant component in sparse random graphs
• The diameter of sparse random graphs

This page was built for publication: On the Rigidity of Sparse Random Graphs