Distinguishing Vertices of Random Graphs

DOI10.1016/S0304-0208(08)73545-XMaRDI QIDQ3958505zbMATH OpenOpenAlexFDO

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

(19)

• Improved random graph isomorphism
• Exact matching of random graphs with constant correlation
• Robustly self-ordered graphs: constructions and applications to property testing
• Nut graphs with a given automorphism group
• Isomorphism for random \(k\)-uniform hypergraphs
• Local maxima of the systole function
• Enhancing graph representation learning with localized topological features
• Canonization of a random circulant graph by counting walks
• 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
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• Cutting planes width and the complexity of graph isomorphism refutations
• On testing asymmetry in the bounded degree graph model
• On generic complexity of the isomorphism problem for finite semigroups
• Computational complexity of the Weisfeiler-Leman dimension
• Computational complexity of the Weisfeiler-Leman dimension
• Average-case and smoothed analysis of graph isomorphism

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)