Almost universal graphs

DOI10.1002/RSA.20121MaRDI QIDQ5486325zbMATH OpenOpenAlexDBLPWikidataFDO

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

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

Recommendations

• Explicit sparse almost-universal graphs for G (n, 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)

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

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)