- Journal Article
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 Erdos-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 Delta(k,infinity)(n) the minimum possible maximum degree of a k-additive spanner of Q(n), Arizumi-Hamburger-Kostochka showed that n/ln n e(-4k) <= Delta(2k,infinity)(n) <= 20 n/ln n ln ln n. We improve their upper bound by showing that Delta(2k,infinity)(n) <= 10(4k) n/ln n ln((k+1)) n, where the last term denotes a k + 1-fold iterated logarithm. Show more
Journal / seriesThe Electronic Journal of Combinatorics
Pages / Article No.
PublisherElectronic Journal of Combinatorics
Organisational unit03993 - Sudakov, Benjamin / Sudakov, Benjamin
175573 - Extremal problems in combinatorics (SNF)
MoreShow all metadata