Optimal universal graphs with deterministic embedding

Abstract

Let H be a finite family of graphs. A graph G is H-universal if it contains a copy of each H ∈ H as a subgraph. Let H(k, n) denote the family of graphs on n vertices with maximum degree at most 2 2 − k. For all admissible k and n, we construct an H(k, n)-universal graph G with at most ckn k edges, where ck is a constant depending only on k. This is optimal, up to the constant factor ck, as it is known that c ′ kn2−2/k is a lower bound for the number of edges in any such graph. The construction of G is explicit, and there is an efficient deterministic algorithm for finding a copy of any given H ∈ H(k, n) in G. 1