Almost universal graphs

DOI10.1002/RSA.20121MaRDI QIDQ5486325zbMATHOpenAlexDBLPWikidataFDO

Authors Michael Krivelevich, Alan Frieze

Publication date 6 September 2006

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20121

zbMATH Keywords

phase transitionsubgraphs of random graphsuniversal graphs for bounded-degree graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Explicit sparse almost-universal graphs for \(\mathcal G (n, \frac kn)\)
• Almost-spanning universality in random graphs
• Almost-spanning universality in random graphs (extended abstract)
• Universality of random graphs
• scientific article; zbMATH DE number 1882352

Cited in

(15)

• Almost every \(n\)-vertex graph is determined by its \(3 \log_2n\)-vertex subgraphs
• scientific article; zbMATH DE number 4170938 (Why is no real title available?)
• Almost all cop-win graphs contain a universal vertex
• Explicit sparse almost-universal graphs for \(\mathcal G (n, \frac kn)\)
• Feasible graphs with standard universe
• An improved upper bound on the density of universal random graphs
• Expanders are universal for the class of all spanning trees
• scientific article; zbMATH DE number 1882352 (Why is no real title available?)
• Properties of Almost All Graphs and Generalized Quantifiers
• Universal geometric graphs
• Universally signable graphs
• Some remarks on universal graphs
• Graph Traversals as Universal Constructions
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Expanders Are Universal for the Class of All Spanning Trees

This page was built for publication: Almost universal graphs

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