### Abstract

For every n, we describe an explicit construction of a graph on n vertices with at most O(n^{2-ε}) 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 Ω(n^{4/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 Θ(n^{2}/(log^{2} n)). This improves a result of Babai, Chung, Erdös, Graham and Spencer (Ann. Discrete Math. 12 (1982) 21-26).

Original language | English (US) |
---|---|

Pages (from-to) | 1-11 |

Number of pages | 11 |

Journal | Journal of Computational and Applied Mathematics |

Volume | 142 |

Issue number | 1 |

DOIs | |

State | Published - May 1 2002 |

### All Science Journal Classification (ASJC) codes

- Computational Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Sparse universal graphs'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Asodi, V. (2002). Sparse universal graphs.

*Journal of Computational and Applied Mathematics*,*142*(1), 1-11. https://doi.org/10.1016/S0377-0427(01)00455-1