Optimal induced universal graphs for bounded-degree graphs

Noga Alon, Rajko Nenadov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

We show that for any constant δ ≥ 2, there exists a graph T 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 of Esperet et al. and is optimal up to a constant factor, as it is known that any such graph must have at least (n δ =2) vertices. Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of T is explicit and is based on an appropriately defined composition of high-girth expander graphs. The proof also provides an efficient deterministic procedure for finding, for any given input graph H on n vertices with maximum degree at most Δ, an induced subgraph of T isomorphic to H.

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
PublisherAssociation for Computing Machinery
Pages1149-1157
Number of pages9
ISBN (Electronic)9781611974782
DOIs
StatePublished - Jan 1 2017
Externally publishedYes
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 19 2017

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume0

Other

Other28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
CountrySpain
CityBarcelona
Period1/16/171/19/17

All Science Journal Classification (ASJC) codes

  • Software
  • 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

    Alon, N., & Nenadov, R. (2017). Optimal induced universal graphs for bounded-degree graphs. In P. N. Klein (Ed.), 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (pp. 1149-1157). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 0). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974782.74