Bounded degree spanners of the hypercube

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

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

D e l t a_{k, i n f t y} (n)

the minimum possible maximum degree of a

k

-additive spanner of

Q_{n}

, Arizumi--Hamburger--Kostochka showed that

frac{n}{ln n}e^{-4k}leq Delta_{2k,infty}(n)leq 20frac{n}{ln n}ln ln n.

We improve their upper bound by showing that

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.

Review text

Summary: 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 \textit{P. Erdős} et al. [J. Graph Theory 23, No. 2, 119--128 (1996; Zbl 0857.05027)], 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,\infty}(n)\) the minimum possible maximum degree of a \(k\)-additive spanner of \(Q_n\), \textit{N. Arizumi} et al. [ibid. 57, No. 1, 55--64 (2008; Zbl 1203.05110)] showed that \[\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 \[\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.

Recommendations

Cites work

Cited in

(4)

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)