Optimal induced universal graphs for bounded-degree graphs

Noga Alon; Rajko Nenadov

doi:10.1017/S0305004117000706

Optimal induced universal graphs for bounded-degree graphs

Noga Alon, Rajko Nenadov

Research output: Contribution to journal › Article › peer-review

3 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 language	English (US)
Pages (from-to)	61-74
Number of pages	14
Journal	Mathematical Proceedings of the Cambridge Philosophical Society
Volume	166
Issue number	1
DOIs	https://doi.org/10.1017/S0305004117000706
State	Published - Jan 1 2019
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1017/S0305004117000706

Cite this

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

}

TY - JOUR

T1 - Optimal induced universal graphs for bounded-degree graphs

AU - Alon, Noga

AU - Nenadov, Rajko

PY - 2019/1/1

Y1 - 2019/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85031502599&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031502599&partnerID=8YFLogxK

U2 - 10.1017/S0305004117000706

DO - 10.1017/S0305004117000706

M3 - Article

AN - SCOPUS:85031502599

SN - 0305-0041

VL - 166

SP - 61

EP - 74

JO - Mathematical Proceedings of the Cambridge Philosophical Society

JF - Mathematical Proceedings of the Cambridge Philosophical Society

IS - 1

ER -

Optimal induced universal graphs for bounded-degree graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this