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 -