### Abstract

We show that for any constant δ ≥ 2, there exists a graph T with O(nδ=2) vertices which contains every n-vertex graph with maximum degree Δ as an induced subgraph. For odd Δ this significantly improves the best-known earlier bound of Esperet et al. and is optimal up to a constant factor, as it is known that any such graph must have at least (n δ =2) vertices. Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of T is explicit and is based on an appropriately defined composition of high-girth expander graphs. The proof also provides an efficient deterministic procedure for finding, for any given input graph H on n vertices with maximum degree at most Δ, an induced subgraph of T isomorphic to H.

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

Title of host publication | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 |

Editors | Philip N. Klein |

Publisher | Association for Computing Machinery |

Pages | 1149-1157 |

Number of pages | 9 |

ISBN (Electronic) | 9781611974782 |

DOIs | |

State | Published - Jan 1 2017 |

Externally published | Yes |

Event | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain Duration: Jan 16 2017 → Jan 19 2017 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 0 |

### Other

Other | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 |
---|---|

Country | Spain |

City | Barcelona |

Period | 1/16/17 → 1/19/17 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

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

## Cite this

*28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017*(pp. 1149-1157). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 0). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974782.74