@article{8fe09076c34845bc8bf140636c8073bf,
title = "Optimal induced universal graphs for bounded-degree graphs",
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.",
author = "Noga Alon and Rajko Nenadov",
note = "Funding Information: Research supported in part by a USA-Israeli BSF grant 2012/107, by an ISF grant 620/13 and by the Israeli I-Core program. Funding Information: ALON NOGA † NENADOV RAJKO Sackler School of Mathematics and Blavatnik School of Computer Science , Tel Aviv University , Tel Aviv 69978 , Israel . e-mail: nogaa@tau.ac.il School of Mathematical Sciences , Monash University , VIC 3800 , Australia . e-mail: rajko.nenadov@monash.edu † Research supported in part by a USA-Israeli BSF grant 2012/107, by an ISF grant 620/13 and by the Israeli I-Core program. 01 2019 11 10 2017 166 1 61 74 19 12 2016 Copyright {\textcopyright} Cambridge Philosophical Society 2017 2017 Cambridge Philosophical Society Publisher Copyright: Copyright {\textcopyright} 2017 Cambridge Philosophical Society.",
year = "2019",
month = jan,
day = "1",
doi = "10.1017/S0305004117000706",
language = "English (US)",
volume = "166",
pages = "61--74",
journal = "Mathematical Proceedings of the Cambridge Philosophical Society",
issn = "0305-0041",
publisher = "Cambridge University Press",
number = "1",
}