Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T10:33:14.488Z Has data issue: false hasContentIssue false

Optimal induced universal graphs for bounded-degree graphs

Published online by Cambridge University Press:  11 October 2017

NOGA ALON
Affiliation:
Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. e-mail: nogaa@tau.ac.il
RAJKO NENADOV
Affiliation:
School of Mathematical Sciences, Monash University, VIC 3800, Australia. e-mail: rajko.nenadov@monash.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 2017