Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

DOI10.4230/LIPICS.ICALP.2017.128zbMATH Open1447.05179arXiv1607.04911MaRDI QIDQ5111460FDOQ5111460

Authors: Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, Morten Stöckel 

Publication date: 27 May 2020

Abstract: A graph $U$ is an induced universal graph for a family $F$ of graphs if every graph in $F$ is a vertex-induced subgraph of $U$. For the family of all undirected graphs on $n$ vertices Alstrup, Kaplan, Thorup, and Zwick [STOC 2015] give an induced universal graph with $O!left(2^{n/2}ight)$ vertices, matching a lower bound by Moon [Proc. Glasgow Math. Assoc. 1965]. Let $k=lceilD/2ceil$. Improving asymptotically on previous results by Butler [Graphs and Combinatorics 2009] and Esperet, Arnaud and Ochem [IPL 2008], we give an induced universal graph with $O!left(frack{2}^{k}k!n^{k}ight)$ vertices for the family of graphs with $n$ vertices of maximum degree $D$. For constant $D$, Butler gives a lower bound of $Omega!left(n^{D/2}ight)$. For an odd constant $Dgeq3$, Esperet et al. and Alon and Capalbo [SODA 2008] give a graph with $O!left(n^{k-frac1D}ight)$ vertices. Using their techniques for any (including constant) even values of $D$ gives asymptotically worse bounds than we present. For large $D$, i.e. when $D=Omegaleft(lo{g}^{3}night)$, the previous best upper bound was $nchooselceilD/2ceil{n}^{O(1)}$ due to Adjiashvili and Rotbart [ICALP 2014]. We give upper and lower bounds showing that the size is $lfloorn/2floorchooselfloorD/2floor{2}^{pmildeOleft(sqrtDight)}$. Hence the optimal size is $2^{ildeO(D)}$ and our construction is within a factor of $2^{ildeOleft(sqrtDight)}$ from this. The previous results were larger by at least a factor of $2^{Omega(D)}$. As a part of the above, proving a conjecture by Esperet et al., we construct an induced universal graph with $2n-1$ vertices for the family of graphs with max degree $2$. In addition, we give results for acyclic graphs with max degree $2$ and cycle graphs. Our results imply the first labeling schemes that for any $D$ are at most $o(n)$ bits from optimal.

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

Recommendations

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

zbMATH Keywords

distributed computingbounded-degree graphsinduced universal graphsadjacency labeling schemes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Vertex degrees (05C07) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cited In (7)

• On induced-universal graphs for the class of bounded-degree graphs
• Universal graphs and induced-universal graphs
• Near-optimal induced universal graphs for cycles and paths
• An adjacency labeling scheme based on a decomposition of trees into caterpillars
• Optimal induced universal graphs for bounded-degree graphs
• Optimal induced universal graphs for bounded-degree graphs
• Induced-universal graphs for graphs with bounded maximum degree

This page was built for publication: Near-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 Q5111460)