Optimal induced universal graphs for bounded-degree graphs

Noga Alon, Rajko Nenadov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish (US)
Pages (from-to)61-74
Number of pages14
JournalMathematical Proceedings of the Cambridge Philosophical Society
Volume166
Issue number1
DOIs
StatePublished - Jan 1 2019
Externally publishedYes

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