Bounded degree spanners of the hypercube

DOI10.37236/9074zbMath1444.05103arXiv1910.09868MaRDI QIDQ782941

Rajko Nenadov, Mehtab Sawhney, Adam Zsolt Wagner, Benjamin Sudakov

Publication date: 29 July 2020

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

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

zbMATH Keywords

\(k\)-additive spanners; bounded degree subgraph

Mathematics Subject Classification ID

05C65: Hypergraphs

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

05C07: Vertex degrees

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)