@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",

}