Sparse universal graphs

摘要

For every n, we describe an explicit construction of a graph on n vertices with at most O(n2−ε) edges, for ε=0.133…, that contains every graph on n vertices with maximum degree 3 as a subgraph. It is easy to see that each such graph must have at least Ω(n4/3) edges. We also show that the minimum number of edges of a graph that contains every graph with n edges as a subgraph is Θ(n2/(log2n)). This improves a result of Babai, Chung, Erdös, Graham and Spencer (Ann. Discrete Math. 12 (1982) 21–26).