### Abstract

Let ℋ be a family of graphs. A graph T is ℋ-universal if it contains a copy of each H ∈ ℋ as a subgraph. Let ℋ(k, n) denote the family of graphs on n vertices with maximum degree at most k. For all positive integers k and n, we construct an ℋ(k, n)-universal graph T with O_{k}(n^{2-2/k} log^{4/k} n) edges and exactly n vertices. The number of edges is almost as small as possible, as Ω(n ^{2-2/k}) is a lower bound for the number of edges in any such graph. The construction of T is explicit, whereas the proof of universality is probabilistic and is based on a novel graph decomposition result and on the properties of random walks on expanders.

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

Pages (from-to) | 123-133 |

Number of pages | 11 |

Journal | Random Structures and Algorithms |

Volume | 31 |

Issue number | 2 |

DOIs | |

State | Published - Sep 1 2007 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

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

## Cite this

Alon, N., & Capalbo, M. (2007). Sparse universal graphs for bounded-degree graphs.

*Random Structures and Algorithms*,*31*(2), 123-133. https://doi.org/10.1002/rsa.20143