Bounded degree spanners of the hypercube

DOI10.37236/9074MaRDI QIDQ782941zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

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)