Bounded degree spanners of the hypercube

DOI10.37236/9074zbMATH Open1444.05103arXiv1910.09868OpenAlexW3042057333MaRDI QIDQ782941FDOQ782941

Authors: Rajko Nenadov, Mehtab Sawhney, Adam Zsolt Wagner, Benny Sudakov 

Publication date: 29 July 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this short note we study two questions about the existence of subgraphs of the hypercube $Q_n$ with certain properties. The first question, due to ErdH{o}s--Hamburger--Pippert--Weakley, asks whether there exists a bounded degree subgraph of $Q_n$ which has diameter $n$. We answer this question by giving an explicit construction of such a subgraph with maximum degree at most 120. The second problem concerns properties of $k$-additive spanners of the hypercube, that is, subgraphs of $Q_n$ in which the distance between any two vertices is at most $k$ larger than in $Q_n$. Denoting by $Delt{a}_{k,infty}(n)$ the minimum possible maximum degree of a $k$-additive spanner of $Q_n$, Arizumi--Hamburger--Kostochka showed that ${\displaystyle }$frac{n}{ln n}e^{-4k}leq Delta_{2k,infty}(n)leq 20frac{n}{ln n}ln ln n.${\displaystyle }$ We improve their upper bound by showing that ${\displaystyle }$Delta_{2k,infty}(n)leq 10^{4k} frac{n}{ln n}ln^{(k+1)}n,${\displaystyle }$where the last term denotes a $k+1$-fold iterated logarithm.

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

Recommendations

• Spanners of Hypercube-Derived Networks
• Sparse hypercube 3-spanners
• Some small sized spanning subgraphs of a hypercube
• scientific article; zbMATH DE number 568803
• Hypercube subgraphs with local detours

zbMATH Keywords

\(k\)-additive spannersbounded degree subgraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex degrees (05C07) Distance in graphs (05C12) Hypergraphs (05C65)

Cites Work

• Additive graph spanners
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• New additive spanners
• A survey of integrity
• On plane geometric spanners: a survey and open problems
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• On 2-detour subgraphs of the hypercube
• Two results about the hypercube
• Graph spanners: a tutorial review
• Onk-detour subgraphs of hypercubes
• Title not available (Why is that?)
• Generating Low-Degree 2-Spanners
• The 4/3 additive spanner exponent is tight
• Title not available (Why is that?)
• Hypercube subgraphs with minimal detours

Cited In (4)

• Hypercube subgraphs with local detours
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• Sparse hypercube 3-spanners
• On 2-detour subgraphs of the hypercube

This page was built for publication: Bounded degree spanners of the hypercube

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