### Abstract

We show that for any constant Δ ≥ 2, there exists a graph Γ 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 and is optimal up to a constant factor, as it is known that any such graph must have at least Ω(n ^{Δ/2} ) vertices.

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

Pages (from-to) | 61-74 |

Number of pages | 14 |

Journal | Mathematical Proceedings of the Cambridge Philosophical Society |

Volume | 166 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2019 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- 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

Alon, N., & Nenadov, R. (2019). Optimal induced universal graphs for bounded-degree graphs.

*Mathematical Proceedings of the Cambridge Philosophical Society*,*166*(1), 61-74. https://doi.org/10.1017/S0305004117000706