Optimal induced universal graphs for bounded-degree graphs

DOI10.1137/1.9781611974782.74MaRDI QIDQ4575816zbMATH OpenOpenAlexWikidataFDO

Authors Noga Alon, Rajko Nenadov

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.03234

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: We show that for any constant $Deltage2$, there exists a graph $G$ with $O(n^{Delta/2})$ vertices which contains every $n$-vertex graph with maximum degree $Delta$ as an induced subgraph. For odd $Delta$ 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 $Omega(n^{Delta/2})$ vertices. Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of $G$ 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 $Delta$, an induced subgraph of $G$ isomorphic to $H$.

Recommendations

• Optimal induced universal graphs for bounded-degree graphs
• Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
• Induced-universal graphs for graphs with bounded maximum degree
• On induced-universal graphs for the class of bounded-degree graphs
• Asymptotically optimal induced universal graphs
• scientific article; zbMATH DE number 1833411
• Near-optimal induced universal graphs for cycles and paths
• Optimal induced universal graphs and adjacency labeling for trees
• Sparse universal graphs for bounded‐degree graphs
• Universal graphs and induced-universal graphs

Cited in

(12)

• Induced-universal graphs for graphs with bounded maximum degree
• On induced-universal graphs for the class of bounded-degree graphs
• Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
• Better distance labeling for unweighted planar graphs
• Adjacency labeling schemes and induced-universal graphs
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Fault-tolerant distance labeling for planar graphs
• Fault-tolerant distance labeling for planar graphs
• Better distance labeling for unweighted planar graphs
• Induced universal hypergraphs
• scientific article; zbMATH DE number 7765385 (Why is no real title available?)
• Optimal induced universal graphs for bounded-degree graphs

This page was built for publication: Optimal induced universal graphs for bounded-degree graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575816)