Optimal induced universal graphs for bounded-degree graphs

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 suc...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical proceedings of the Cambridge Philosophical Society 2019-01, Vol.166 (1), p.61-74
Main Authors: ALON, NOGA, NENADOV, RAJKO
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0041
1469-8064
DOI:10.1017/S0305004117000706