TY - GEN

T1 - Optimal induced universal graphs for bounded-degree graphs

AU - Alon, Noga

AU - Nenadov, Rajko

N1 - Publisher Copyright:
Copyright © by SIAM.

PY - 2017

Y1 - 2017

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

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

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

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

U2 - 10.1137/1.9781611974782.74

DO - 10.1137/1.9781611974782.74

M3 - Conference contribution

AN - SCOPUS:85016173221

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1149

EP - 1157

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

A2 - Klein, Philip N.

PB - Association for Computing Machinery

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Y2 - 16 January 2017 through 19 January 2017

ER -