{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:55Z","timestamp":1753893835683,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>\u00a0In 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 Erd\u0151s\u2013Hamburger\u2013Pippert\u2013Weakley, asks whether there exists a bounded degree subgraph of $Q_n$ which has diameter $n$. We answer this question\u00a0 by giving an explicit construction of such a subgraph with maximum degree at most 120.\r\nThe 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 $\\Delta_{k,\\infty}(n)$ the minimum possible maximum degree of a $k$-additive spanner of $Q_n$, Arizumi\u2013Hamburger\u2013Kostochka showed that\u00a0\u00a0$$\\frac{n}{\\ln n}e^{-4k}\\leq \\Delta_{2k,\\infty}(n)\\leq 20\\frac{n}{\\ln n}\\ln \\ln n.$$ We improve their upper bound by showing that\u00a0\u00a0 \u00a0 $$\\Delta_{2k,\\infty}(n)\\leq 10^{4k} \\frac{n}{\\ln n}\\ln^{(k+1)}n,$$where the last term denotes a $k+1$-fold iterated logarithm.<\/jats:p>","DOI":"10.37236\/9074","type":"journal-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T01:56:28Z","timestamp":1594259788000},"source":"Crossref","is-referenced-by-count":1,"title":["Bounded Degree Spanners of the Hypercube"],"prefix":"10.37236","volume":"27","author":[{"given":"Rajko","family":"Nenadov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mehtab","family":"Sawhney","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam Zsolt","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2020,7,10]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v27i3p3\/8123","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v27i3p3\/8123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T01:56:28Z","timestamp":1594259788000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v27i3p3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,10]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2020,7,9]]}},"URL":"https:\/\/doi.org\/10.37236\/9074","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2020,7,10]]},"article-number":"P3.3"}}