Distinguishing Vertices of Random Graphs

DOI10.1016/S0304-0208(08)73545-XzbMATH Open0495.05057OpenAlexW12328562MaRDI QIDQ3958505FDOQ3958505

Authors: Béla Bollobás 

Publication date: 1982

Published in: Graph Theory, Proceedings of the Conference on Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-0208(08)73545-x

zbMATH Keywords

distance sequencerandom labelled graphrandom r-regular graphs

Mathematics Subject Classification ID

Combinatorial probability (60C05) Graph theory (05C99)

Cited In (13)

• Improved random graph isomorphism
• Isomorphism for random \(k\)-uniform hypergraphs
• Canonization of a random circulant graph by counting walks
• Local maxima of the systole function
• Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm
• Distance degree regular graphs and distance degree injective graphs: an overview
• Efficient random graph matching via degree profiles
• Random quantum graphs
• Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis
• Cutting planes width and the complexity of graph isomorphism refutations
• Title not available (Why is that?)
• Exact matching of random graphs with constant correlation
• Robustly self-ordered graphs: constructions and applications to property testing

This page was built for publication: Distinguishing Vertices of Random Graphs

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