On Graphs Which Contain All Sparse Graphs
Let \(s(n)\) denote the maximum number of edges in a graph \(G\) which contains as subgraphs all graphs with \(n\) edges. The authors prove that for sufficiently large \(n\) \(cn^2/\log^2n<s(n)<c'n^2\log\log n/\log n\) (here \(c\) and \(c'\) are constants). It is also proved that the minimum number of edges in a graph which contains all planal graphs with \(n\) edges is less than \(cn^{3/2}\). The proofs are prohabilistic (which might not be a surprise) and short (10\% of the paper is taken up by redoubtable list of authors). For the entire collection see [Zbl 0485.00006].
- Sparse universal graphs
- Sparse multipartite graphs as partition universal for graphs with bounded degree
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Universality of random graphs and rainbow embedding
- Perfect Storage Representations for Families of Data Structures
- Explicit sparse almost-universal graphs for G (n, kn)
- Universality, tolerance, chaos and order
- Almost-spanning universality in random graphs (extended abstract)
- Every graph is contained in a sparsest possible balanced graph
- Maximum planar subgraphs in dense graphs
- scientific article; zbMATH DE number 125475 (Why is no real title available?)
- Adjacency labeling schemes and induced-universal graphs
- Optimal threshold for a random graph to be 2-universal
- Über die in Graphen enthaltenen saturierten planaren Graphen
- Almost-spanning universality in random graphs
- Expanders are universal for the class of all spanning trees
- Shorter Labeling Schemes for Planar Graphs
- Universal and unavoidable graphs
- On unavoidable graphs
- Sparse universal graphs for planarity
- Packing topological minors half‐integrally
- Graph product structure for non-minor-closed classes
- Universal geometric graphs
- A note on universal graphs for spanning trees
- Universality for graphs with bounded density
- Universality for graphs of bounded degeneracy
- On universal hypergraphs
- Tight bounds for hypercube minor-universality
- Subgraph-universal planar graphs for trees
- Faithful universal graphs for minor-closed classes
- Induced-universal graphs for graphs with bounded maximum degree
This page was built for publication: On Graphs Which Contain All Sparse Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3958492)